Problem F: Chocolate Chip Cookies
Making chocolate chip cookies involves mixing flour, salt, oil, baking soda and
chocolate chips to form dough which is rolled into a plane about
50 cm square. Circles are cut from the plane, placed on a cookie
sheet, and baked in an oven for about twenty minutes. When the cookies
are done, they are removed from the oven and allowed to cool before
being eaten.
We are concerned here with the process of cutting the first cookie after
the dough has been rolled. Each chip is visible in the planar dough,
so we need simply to place the cutter so as to maximize the number
of chocolate chips contained in its perimeter.
Input Specification
First line of input contains an integer N≤10. Then N test cases follow, each
starting with integer M≤200, the number of chocolate chip cookies.
Next M lines contain pairs of floating
point numbers indicating the (x,y) coordinates of a chip in the square
surface of cookie dough (see the example below). Each coordinate is between 0.0 and 50.0 (cm).
Each chip may be considered a point (i.e. these are not President's Choice
Cookies). Each chip is at a different position.
Output Specification
For each test case output a single integer on its own line: the number of chocolate
chips that can be contained in a single cookie whose diameter is 5 cm.
The cookie need not be fully contained in the 50 cm square dough (i.e.
it may have a flat side).
Sample Input
1
8
4.0 4.0
4.0 5.0
5.0 6.0
1.0 20.0
1.0 21.0
1.0 22.0
1.0 25.0
1.0 26.0
Output for Sample Input
4