Most Points on a Line

Difficulty: 1800 6000 ms 128 MB

geometry

Print the maximum number of the given points that lie on a single straight line.

Input: the first line has N; the next N lines have distinct points x y.

Output: the largest collinear subset size.

Constraints:

• 1 ≤ N ≤ 3000
• |coordinates| ≤ 10⁴

Sample Tests

5
0 0
1 1
2 2
1 0
0 1

3

1
5 5

1

Read the Editorial