LeetCode 149. Max Points on a Line 多少个点共线

# Definition for a point.
# class Point(object):
#     def __init__(self, a=0, b=0):
#         self.x = a
#         self.y = b

class Solution(object):
    def maxPoints(self, points):
        """
        :type points: List[Point]
        :rtype: int
        """
        n = len(points)
        if n==0: return 0
        ans = 1
        for i in xrange(n):
            dic = {}
            inf = []
            temp = 1
            for j in xrange(n):
                if i==j:continue
                if points[i].x == points[j].x and points[i].y == points[j].y:
                    temp += 1
                    continue
                if points[i].x == points[j].x:
                    inf.append(j)
                else :
                    value = 1.0*(points[i].y - points[j].y)/(points[i].x - points[j].x)
                    if dic.has_key(value):
                        dic[value].append(j)
                    else:
                        dic[value] = [j]
        
            for key in dic.keys():
                ans = max(ans, len(dic[key]) + temp)
            ans = max(ans, len(inf) + temp)
        
        return ans