leetcode 149: 直线上最多的点数

给定一个二维平面，平面上有 n 个点，求最多有多少个点在同一条直线上。

示例 1:

输入: [[1,1],[2,2],[3,3]]
输出: 3
解释:
^
|
|        o
|     o
|  o  
+------------->
0  1  2  3  4
示例 2:

输入: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出: 4
解释:
^
|
|  o
|     o        o
|        o
|  o        o
+------------------->
0  1  2  3  4  5  6

这道题很自然就能想到计算斜率，哈希表存储，但是需要注意几个点：
1、斜率无穷大的特殊情况
2、有相同点的情况
3、特殊测试用例：[[0,0],[94911151,94911150],[94911152,94911151]] 浮点数精度不够

解决方案：
1、哈希表加一个键
2、用same存储相同点的个数
3、用dx/dy代替dy/dx可以去除这种浮点数精度不够的情况，但只是针对这一个样例；另一个方法：使用Decimal。

from decimal import Decimal
Decimal((point[1][1] - point[0][1]))/Decimal((point[1][0] - point[0][0]))

牺牲了一些计算上的耗时。

完整代码：

class Solution(object):
    def maxPoints(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        length = len(points)
        if length < 3: return length
        max_points = 0
        for i in range(length):
            d = {'inf':0}
            same = 1
            for j in range(i,length):
                if i == j:
                    continue
                if points[i][1] == points[j][1] and points[i][0] != points[j][0]:
                    d['inf'] += 1
                elif points[i][0] != points[j][0]:
                    k = 1.0 * (points[i][0] - points[j][0])/(points[i][1] - points[j][1])
                    if k not in d:
                        d[k] = 1
                    else:
                        d[k] += 1
                else:
                    same += 1 
            max_points = max(max_points, max(d.values()) + same)
        return max_points