Hide

Problem D
Fruit Slicer

/problems/fruitslicer/file/statement/en/img-0001.png
John, a student who is taking the game development course, recently developed a mobile game called Fruit Slicer for his coursework. In the game the player slices fruits that are throw into the air by swiping the touch screen. However the game is quite simple because John was not able to write code for the geometry required for a more complex version. In the game each slice is a straight line of infinite length, and all fruits have the same shape of a circle with unit radius. The figure shows a cool snapshot of John’s game.

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

Please log in to submit a solution to this problem

Log in