ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Junior Contest October'2004

About     Problems     Submit solution     Judge status     Standings
Contest is over

F. Genie Bomber

Time limit: 1.0 second
Memory limit: 64 MB
The last survivor was a certain Pitirim Schwartz, an erstwhile monk and inventor of the forked musket rest, who was selflessly laboring on the genie-bomber project. The essence of the project was to drop on the enemy cities bottles with genies who had been held imprisoned no less than three thousand years. It is well known that genies in their free state are capable only of destroying cities or constructing palaces. A thoroughly aged genie, reasoned Schwartz, was not about to start building palaces, and therefore things would go badly for the enemy. A definite obstacle to the realization of this concept was an insufficient supply of bottled genies, but Schwartz counted on overcoming this through the deep dragging of the Red and Mediterranean Seas.
The genie-bomber project has eventually entered the experimentation stage. Research fellows’ doubles have constructed N cities in the testing area. Each of these cities is a circle with a radius of r. As M. M. Kamnoedov provided only one bottled genie for the experiment, experimenters decided to demolish as many cities as possible for the sake of science. It is generally known that a genie demolishes everything in the range of R around the bottle’s touchdown point. Any city contained completely within this demolition area is ruined. Before the experiment is conducted, you are required to find the maximum possible number of cities that one genie can ruin.


The first line contains the number N of cities (1 ≤ N ≤ 100). The following N lines contain the coordinates xi, yi of city centers (xi, yi are integers, |xi|, |yi| ≤ 10000). City centers don’t coincide with each other.
The last line contains radius R of the genie’s area of destruction and the city radius r (1 ≤ R, r ≤ 10000). R and r are integers.


Output the maximum number of cities that can be destroyed by one bottled genie.


0 0
0 4
4 0
3 1
0 0
0 1
0 2
0 3
0 4
1 1
Problem Author: Alexander Bikbaev
Problem Source: The 10th Collegiate Programming Contest of the High School Pupils of the Sverdlovsk Region (October 16, 2004)
To submit the solution for this problem go to the Problem set: 1332. Genie Bomber