kazi1@的部落格

Given n points on a 2D plane, find the maximum number of points that lie on the same straight 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
        """
        if len(points) < 3:
            return len(points)
        gmax = 0
        for i in xrange(len(points)-1):
            slopes = {}
            lmax = 1  # myself is a point
            for j in xrange(i+1, len(points)):
                if points[i].x == points[j].x:
                    if points[i].y == points[j].y:
                        lmax += 1
                    else:
                        slopes['horz'] = slopes.get('horz', 0) + 1
                else:
                    s = float(points[i].y - points[j].y) / float(points[i].x - points[j].x)
                    slopes[s] = slopes.get(s, 0) + 1

            if len(slopes) > 0:
                lmax += max(slopes.values())
            gmax = max(gmax, lmax)
        return gmax