# 6-liner in Python, Simple solution without GCD

• Simple math: a line can be uniquely represented by `y=ax+b` or `x=c` (vertical-line case).

We can iterate through all pairs of points and find the line that the 2 points are forming. The hash key tuple for the line is either `(a, b)` or `(float('inf'), c)`.

By doing that, all points are grouped by unique lines.

Then we count the number of unique points for each line and return the maximum.

``````class Solution(object):
def maxPoints(self, points):
d = collections.defaultdict(set)
for i in range(1, len(points)):
for j in range(i):
p1, p2 = points[i], points[j]
d[(float('inf'), p1.x) if p1.x==p2.x else ((p1.y-p2.y)/float(p1.x-p2.x), (p1.x*p2.y-p2.x*p1.y)/float(p1.x-p2.x))] |= set([p1, p2])
return max(len(s) for s in d.values()) if len(points)>1 else len(points)
``````

Or the longer but easier-to-read version:

``````class Solution(object):
def maxPoints(self, points):
d = collections.defaultdict(list)
for i in range(1, len(points)):
for j in range(i):
p1, p2 = points[i], points[j]
if p1.x == p2.x:
t = (float('inf'), p1.x)
else:
t = ((p1.y-p2.y)/float(p1.x-p2.x), (p1.x*p2.y-p2.x*p1.y)/float(p1.x-p2.x))
d[t] += [p1, p2]
return max(len(set(l)) for l in d.values()) if len(points)>1 else len(points)
``````

• No need for `(float('inf'), p1.x)`, you can just use `p1.x`. After a few more changes:

``````    def maxPoints(self, points):
d = collections.defaultdict(set)
for p, q in itertools.combinations(points, 2):
d[p.x if p.x==q.x else ((p.y-q.y)/float(p.x-q.x), (p.x*q.y-q.x*p.y)/float(p.x-q.x))] |= {p, q}
return max(map(len, d.values())) if len(points)>1 else len(points)
``````

Btw, thanks for the motivation :-D

• How does python compare two floating point numbers ?
you create a pair t that represents the slope and the intersect and use that in your collection, but what happens if you have precision problems ? Can three points map to the same bucket even though they don't lie on the same line ?
Thanks.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.