Burning Market
Burning Market (100 Marks)
The Chandni Chowk is one of the oldest and busiest markets in Old Delhi, India. Chandni Chowk is located close to Old Delhi Railway Station. Chandni Chowk's speciality is its variety and authenticity: food, delicacies, and sweets of more than 1,000 kinds, sarees with chikan and zari. Narrow lanes host shops sell books, clothing, electronics, consumer goods, shoes, and leather goods. A few years back, there was a fire struck out in the market due to the explosion of a gas cylinder in a sweet shop which spread to many nearby shops and a lot of material damage occurred in this tragedy in such a way that each nearby shop was affected from all 4 sides. You are a fire tender guy and you need to tell which windows are left intact after the fire.
The market consists of P points in the coordinate plane and W windows. Each window connects a pair of points and does not go through any other points. The market has the following additional properties:
- No two windows intersect or overlap, but they may touch at endpoints;
- Each window is parallel to either the horizontal or the vertical coordinate axis.
Initially, the entire coordinate plane is free from any fire. At time zero, fire instantly spreading the exterior (space not bounded by windows). After exactly one hour, every window with fire on one side and without fire on the other; breaks under the pressure of the gas. The fire then spreads in the new area not bounded by any standing windows. Now, there may be new windows having fire on one side and without fire on the other. After another hour, these windows also break down and fire spreads further. This procedure repeats until fire spreads in the entire area.
An example of the process is shown in the following figure.
Figure 1: The state at time zero. Shaded cells represent the fire area, while white cells represent without fire area.
Figure 2: The state after one hour.
Figure 3: The state after two hours. Fire spreads in the entire area and the 4 remaining windows cannot be broken down
Input Format
Input 1: It will be an integer P, the number of points in the plane.
Input 2: It will be a string array where:
First line tells the total number of rows in string array, P
Input 2: It will be a string array where:
First line tells the total number of rows in string array, P
Each of the following P lines contains two integers X and Y (both between 0 and 1000000, inclusive) separated by space, the coordinates of one point. The points are numbered 1 to P in the order in which they are given. No two points will be located at the same coordinates.
Input 3: It will be an integer W, the number of windows.
Input 4: It will be a string array where:
First line tells the total number of rows in string array, W
Input 4: It will be a string array where:
First line tells the total number of rows in string array, W
Each of the following W lines contains two different integers A and B separated by space, meaning that, before the fire, there was a window connecting points A and B. The windows are numbered 1 to W in the order in which they are given.
Constraints
2 ≤ P ≤ 100000
1 ≤ W ≤ 2P1 ≤ A ≤ P, 1 ≤ B ≤ P
Output Format
It will be a single integer K, the number of windows left standing after the fire.Sample TestCase 1
Input
15
15
1 1
8 1
4 2
7 2
2 3
4 3
6 3
2 5
4 5
6 5
4 6
7 6
1 8
4 8
8 8
17
17
1 2
2 15
15 14
14 13
13 1
14 11
11 12
12 4
4 3
3 6
6 5
5 8
8 9
9 11
9 10
10 7
7 6
Output
4
Comments
Post a Comment