max-points-on-a-line

max-points-on-a-line.py

# Definition for a point.
# class Point:
#     def __init__(self, a=0, b=0):
#         self.x = a
#         self.y = b
# 68ms
# Definition for a point.
# class Point:
#     def __init__(self, a=0, b=0):
#         self.x = a
#         self.y = b
class Solution:
    # y = ax + b
    
    def get_slope_repr(self, p, q):
        m, n = p, q
        while n:
            m, n = n, m % n
        p, q = p // m, q // m
        if p < 0 and q > 0:
            p, q = -p, -q
        return p, q

    def maxPoints(self, points):
        """
        :type points: List[Point]
        :rtype: int
        """
        n = len(points)
        if n < 3:
            return n
        n_max = 0
        for i, p1 in enumerate(points):
            all_repr = {}
            if n_max > n - i:
                return n_max
            offset = 1
            for p2 in points[i + 1:]:
                if p2.x == p1.x:
                    if p2.y == p1.y:
                        offset += 1
                        continue
                    a = "Inf"
                else:
                    a = self.get_slope_repr(p2.y - p1.y, p2.x - p1.x)
                all_repr[a] = all_repr.get(a, 0) + 1
            n_max_i = max(all_repr.values()) if all_repr else 0
            n_max = max(n_max, n_max_i + offset)
        return n_max