**Solution with discussion** https://discuss.leetcode.com/topic/75076/python-solution-with-detailed-explanation

**Max Points on a Line** https://leetcode.com/problems/max-points-on-a-line/

**Test all pairs: O(N^2)**

- There can be duplicate points in the list. Dedupe and keep a count of frequency.
- Test every pair and compute the line implied by it. A line is defined by a slope and intercept. But we can avoid maintaining intercept since we can fix a point A, and find all lines from A i.e. AB, AC.
- To compute the slope, use the Fraction class which allows us to define slope as a ratio of numerator and denominator. This class makes sure 6/2 is stored 3/1.

```
# Definition for a point.
# class Point(object):
# def __init__(self, a=0, b=0):
# self.x = a
# self.y = b
from fractions import Fraction
from collections import defaultdict
class Line(object):
def __init__(self, p1x, p1y, p2x, p2y):
m_num, m_den = p2y - p1y, p2x - p1x
if m_den != 0:
f = Fraction(m_num, m_den)
self.slope_key = (f.numerator, f.denominator)
else:
self.slope_key = "INF"
return
class Solution(object):
def dedupe_points(self, points):
pts_freq = defaultdict(int)
for p in points:
pts_freq[(p.x, p.y)] = pts_freq[(p.x, p.y)] + 1
return pts_freq
def maxPoints(self, points):
"""
:type points: List[Point]
:rtype: int
"""
pts_freq = self.dedupe_points(points)
points = [k for k in pts_freq]
if len(points) == 1:
return pts_freq[points[0]]
max_so_far, N = 0, len(points)
for i in range(N):
lines_from_i = {}
for j in range(i+1,N):
p1, p2 = points[i], points[j]
line_slope = Line(p1[0], p1[1], p2[0], p2[1]).slope_key
lines_from_i.setdefault(line_slope, pts_freq[p1])
lines_from_i[line_slope] = lines_from_i[line_slope] + pts_freq[p2]
max_so_far = max(max_so_far, lines_from_i[line_slope])
return max_so_far
```