| ENG RUS | Timus Online Judge |
1332. Genie BomberTime 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. InputThe 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. OutputOutput the maximum number of cities that can be destroyed by one bottled genie. Samples
Problem Author: Alexander Bikbaev Problem Source: The 10th Collegiate Programming Contest of the High School Pupils of the Sverdlovsk Region (October 16, 2004) Tags: geometry |