B. Forest

No Submission Yet

Problem Statement

Andrew went for a walk in the forest behind LHS and got lost. As he sat there waiting for help, he came up with a problem. Of course, he managed to solve it easily, can you do it too?
The forest is a 2D plane, and you are given the coordinates of \(N\) \((1 \leq N \leq 100)\) trees \((x, y)\) \((1 \leq x, y \leq 10^9)\). Your job is to find the largest number of trees that lie on the same line. Note that all coordinates are distinct.

Additional Notes

Time Limit:
C++: 2.5 seconds
Java, Python: 5 seconds
Memory Limit: 128mb


\(1 \leq N \leq 100\)
\(1 \leq x, y \leq 10^9\)

Input format

The first line has one integer \(N\) ― the number of trees.
Each of the next \(N\) lines has two integers \(x\) and \(y\) ― the coordinates of a tree.

Output format

Output one number, the maximum number of trees that lie on the same line.

Sample input:

1 1
2 4
2 2
4 2
3 3

Sample output


Sample Explanation

The maximum number of points on a single line is 3. You can have \((1,1)\), \((2,2)\), and \((3,3)\). Another solution is \((2,4)\), \((3,3)\), and \((4,2)\).

Contact Us
LIT Discord Server