A surveyor places n distinct markers at integer coordinates. Determine the largest number of markers that lie on one straight line. A single marker counts as 1, and any two distinct markers always share a line (count 2).
Line 1: an integer n, the number of markers.
Next n lines: two integers x y, the position of a marker. All positions are distinct.
A single integer: the maximum number of markers on any one line.
Example 1
Input
5 0 0 1 1 2 2 3 3 0 5
Expected
4
Explanation
Four markers lie on the line y = x, and the fifth is off it, so the answer is 4.
Example 2
Input
3 0 0 1 0 0 1
Expected
2
Explanation
No three markers are collinear, so the best any line achieves is 2.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →