Max Points on a Line
Intuition
Solution
class Solution:
def maxPoints(self, points):
"""
:type points: List[Point]
:rtype: int
"""
# Special cases
if not points:
return 0
elif len(points) == 1:
return 1
lines = {}
start = 0
for start in range(len(points)):
for end in range(len(points)):
if start == end:
continue
line = self._get_line(points[start], points[end])
if line not in lines:
lines[line] = set()
for p, index in [[points[start], start], [points[end], end]]:
dim = (p.x, p.y, index)
lines[line].add(dim)
return max([len(v) for v in lines.values()])
def _get_line(self, point1, point2):
x1, y1 = point1.x, point1.y
x2, y2 = point2.x, point2.y
if x2 == x1:
return (x1, None)
k = (y2-y1) * 10 / (x2-x1)
b = y1 - k * x1
return (k, b)