for each point, calculate slopes to all other points. use a hash map to count points with the same slope. handle vertical lines and duplicates separately.
use gcd to normalize slopes to avoid floating point precision issues. the maximum count for any point gives the answer.
key points
- normalize slopes using gcd to avoid precision issues
- handle vertical lines (infinite slope) separately
- count duplicate points separately
- for each point, find max collinear points
complexity
O(n²) time where n is number of points. O(n) space for the slope map.