Problem C : Best Trap
Time Limit: 5 seconds
Construction of your new science lab has just ended. In the floor you have deployed your newly invented equipment.
If deployed beneath the floor, It displays the co-ordinates of points in the floor which are occupied by any material,
even light-weighted ones. They are displayed in a computer which is located in control room.
You are entering the room and switching the equipment on. The under-floor lighting has revealed you that
several mosquitoes are on the floor. Ha ! You have discovered a real-time use for your newly invented equipment.
Conical nets are available with the lab-incharge. You can place a net in the floor and all the mosquitoes inside the net
will be caught. All the mosquitoes that are not caught will fly-off and escape.You have only one attempt.
But you are greedy! You want to catch maximum mosquitoes. You are a brilliant guy. You are rushing to the control room
for co-ordinates of mosquitoes. You decide to catch them so you are asking the lab-incharge for a net.
He gives you a net(CONICAL) of base radius r. He is asking you how many you can catch with that net. Answer him.
Given the size of the room N*N , number of mosquitoes num , Base-radius of net r, which is a double
and co-ordinates of the mosquitoes which are double values, print the maximum number of mosquitoes you can trap.
The centre of the room is taken as the origin 0,0 . So, If size is N, rooms corners are (N/2,N/2) , (-N/2,N/2) ,
(N/2,-N/2) and (-N/2,-N/2).
NOTE:
A mosquitoe at x,y is inside the conical net which is of radius r and at centre x0,y0 iff (x-x0)^2+(y-y0)^2<=r^2
Input Format:
First line contains no. of test cases t.
First line of each test case contains size of room, base radius of net, number of mosquitoes in the format "N r num".
1<=N<=10000 : 0.1<=r<=10000.0 : 1<=num<=15
There are num lines following the first line of the test case, each representing a mosquitoes co-ordinate in the form
"xi yi" -N/2<=xi,yi<=N/2 . The Co-ordinates are floating point numbers.
No leading zeros . Floating point numbers are either in whole number format or in decimal point format.
Co-ordinates for a test case are non-repetitive. (No two xi,yi in a test case is same).
Ouput Format:
Each line should contain the maximum number of mosquitoes that can be trapped for the corresponding test case.
Sample Input:
4
10 0.9 4
0 1
1 0
-1 0
0 -1
10 1 4
0 1
1 0
-1 0
0 -1
10000 0.61 4
1.1 0.1
1.2 0.3
0.4 -2.0
1.1 -0.9
10000 4.7532 4
5 0
3 4
-4 3
2 2
Sample Output:
2
4
3
4
--------------------------------------------------------------------------------------------------------------------------
Problem Setter : Ramgopal K
Written for Samhita '08