
ZOJ Problem Set  3521
Cirno is an ice fairy and lives near the Misty Lake. One day, she found her house was exploded by the Three Mischievous Fairies  Sunny Milk, Luna Child and Star Sapphire. How could Cirno endure this! She was going for revenge and declared war between her and the culprits. Shortly afterwards, she fell into a trap. It is a barrage of bullets. As an ice fairy, she can freeze the bullets around her within a radius R and then, each frozen bullet will form a small ice block with L * L size. The sides of each block are parallel to the Xaxis or Yaxis and the center of each block is located in the position of its corresponding bullet.
If an ice block contains some unfrozen bullets, those bullets will also turn into ice blocks soon. Under this rule, it may cause a chain reaction between bullets. By the way, the reaction is very fast, so you can assume all the bullets are motionless. Give you the coordinates of each bullet and the position of Cirno. Please calculate the number of ice blocks in the end. InputThere are multiple test cases. For each test case: The first line contains three positive integers N (will not greater than 50000), R and L which indicates the number of bullets, the radius of the initial frozen area and the size of each ice block. Then followed by N lines, each line contains two integers X_{i} and Y_{i} represents the position of each bullet. The last line contains two integers X_{0} and Y_{0} represents the position of Cirno. The absolute value of any integer in the input file will not exceed 1,000,000,000. OutputFor each test case, output the number of ice blocks in the end. Sample Input3 3 4 1 1 1 1 2 2 4 1 Sample Output2 Hint
Author: JIANG, Kai 