@shiyanhui

It is vary kind of you to share your idea, and the code works well.

However it makes me a little confused, when it comes to

a, b, c = x1 - x2, y2 - y1, x2 * y1 - x1 * y2

Here is my addition for this to make it clear.

If there are two points (x1, y1), (x2, y2) [x1 != x2, y1 != y2],

and they are in line (y - y1) / (y2 - y1) = (x - x1) / (x2 - x1) ==> (y2 - y1)x + (x1 - x2)y + y1x2 - x1y2 = 0

As a result,

class Solution(object):
def maxPoints(self, points):
"""
:type points: List[Point]
:rtype: int
"""
from collections import defaultdict
result, lens, points = 0, len(points), map(lambda p: (p.x, p.y), points)
for i in range(lens):
x1, y1 = points[i]
same, lines = 1, defaultdict(int)
for j in range(i+1, lens):
x2, y2 = points[j]
if x1 == x2 and y1 == y2:
same += 1
else:
if y2 < y1 or y2 == y2 and x1 < x2:
a, b, c = - y2 + y1, - x1 + x2, - y1 * x2 + y2 * x1
else:
a, b, c = y2 - y1, x1 - x2, y1 * x2 - y2 * x1
rate = self.gcb(self.gcb(a, b), c)
lines[(a / rate, b / rate, c /rate)] += 1
result = max(result, (max(lines.values()) if lines.values() else 0) + same)
return result
def gcb(self, a, b):
while b:
a, b = b, a % b
return a

BTW, the input [[0,0],[94911151,94911150],[94911152,94911151]] will force you to deal with y = k*x + b more carefully.