Problem D
Fruit Slicer
John introduces his game to his best friend Sean, who soon gets bored of playing the simple game. But as a teaching assistant of the algorithm course, Sean decides to turn the game into a homework assignment. He asks the students in the algorithms course to write a program that can compute the best slice at any given moment of the game. Given the locations of the fruits, the program should determine the maximum number of fruits that can be sliced with a single straight-line swipe.
As a student in Sean’s class, you are now the one who is facing this challenge.
Input
The first line has a single integer $n$ ($1 \leq n \leq 100$). The next $n$ lines each have two real numbers giving the $x$ and $y$ coordinates of a fruit. All coordinates have an absolute value no larger than $10^4$ and are given with exactly two digits after the decimal point. Fruits may overlap.
Output
Output the maximum number of fruits that can be sliced with one straight-line swipe. A swipe slices a fruit if the line intersects the inner part or the boundary of the fruit.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 1.00 5.00 3.00 3.00 4.00 2.00 6.00 4.50 7.00 1.00 |
4 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 -1.50 -1.00 1.50 -1.00 0.00 1.00 |
3 |
| Sample Input 3 | Sample Output 3 |
|---|---|
2 1.00 1.00 1.00 1.00 |
2 |
