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 X-axis or Y-axis 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.
There 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 Xi and Yi represents the position of each bullet. The last line contains two integers X0 and Y0 represents the position of Cirno. The absolute value of any integer in the input file will not exceed 1,000,000,000.
For each test case, output the number of ice blocks in the end.
3 3 4 -1 1 1 -1 2 2 4 -1
Author: JIANG, Kai