Max Points on a Line

这个题就是利用三点一线的斜率相等来进行比较，利用哈希表存储斜率，注意斜率无限大以及相同点情况就行，这里有一组LC的case过不去，这是因为Python的精度问题导致的

class Solution(object):
    def maxPoints(self, points):
        """
        :type points: List[Point]
        :rtype: int
        """
        slope = collections.Counter()
        n = len(points)
        result = 0
        cal = lambda x, y: float((y.y - x.y)) / (y.x - x.x)

        def equal(x, y):
            if x.x == y.x:
                if x.y == y.y:
                    return 1
                return 0
            return -1

        for i in xrange(n):
            slope.clear()
            basePoint = points[i]
            duplicate = 1
            slope[-sys.maxint] = 0
            for j in xrange(n):
                if j == i:
                    continue
                elif equal(basePoint, points[j]) == 1:
                    duplicate += 1
                elif equal(basePoint, points[j]) == 0:
                    slope[-sys.maxint] += 1
                else:
                    slope[cal(basePoint, points[j])] += 1

            result = max(result, max(slope.values()) + duplicate)
        return result

可以利用numpy的longdouble类型解决这个问题

import numpy as np

class Solution(object):
    def maxPoints(self, points):
        """
        :type points: List[Point]
        :rtype: int
        """
        result = 0
        n = len(points)
        if n == 1:
            return 1

        cal = lambda x, y: (y.y - x.y) * np.longdouble(1) / (y.x - x.x)

        for i in xrange(n):
            store = collections.Counter()
            same = 1
            for j in xrange(n):
                if i != j:
                    if points[i].x == points[j].x:
                        if points[i].y == points[j].y:
                            same += 1
                        else:
                            store[sys.maxint] += 1
                    else:
                        store[cal(points[i], points[j])] += 1
            if store:
                result = max(result, max(store.values()) + same)
            else:
                result = max(result, same)
            store.clear()

        return result