Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
49 - ZOJ Monthly, December 2005 - 1001
Cover More Circles

Time Limit: 2 Seconds      Memory Limit: 65536 KB

There are some circles on a plane. They may intersect or overlap.You are to place a circle q on this plane (its radium is fixed) and want to cover the maximum possible number of circles. A circle is covered by q if it lies fully inside q.

Input:

This problem contains multiple test cases! Each test case begins with a real number r(r tells the radium of q) and a positive number n(0<n<100,the number of circles on the plane).Then follows n lines ,each describe a circle. Each of the following line contains three real number , the first two describe the x-ax and y-ax of the center of circle,the last one represents for the radium of this circle. Input terminates with the EOF(end of file).

Output:

Output one integer telling the maximum number of circles q can cover in one line for each test case.

Sample Input:
2.0 1 
0.0 0.0 2.0 
4.0 2 
0.0 0.0 2.0 
0.0 1.0 1.0 
Sample Output:
1 
2 

Author: WANG, Yijie


Submit    Status