## Singularity Cup P6 - Explosive Breakout

View as PDF

Points: 30 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem types

A mysterious explosive device resembling a bomb has been planted inside of an abandoned village by an unknown perpetrator.

The village has walls, some of which form enclosed structures. When the bomb explodes, it sends a massive shockwave throughout the entire village. This shockwave attempts to escape outward into open air, causing any walls trapping it to be demolished. More specifically, if the bomb is inside an enclosed structure, it destroys any walls that are on the edge of the smallest simple polygon containing it, and continues to escape outward in the same destructive manner until it reaches open air. A simple polygon with vertices is a shape in the plane which has edges such that has endpoints for all , has endpoints , and the edges do not intersect at all otherwise.

There are points that make up the walls of the village. Each wall connects a pair of points without going through any other walls or points. Additionally, all walls are parallel to either the vertical or horizontal coordinate axis.

Here is an example with the starting point of the bomb represented by a red diamond, and the walls that are about to be destroyed highlighted in red:

The aftermath of the village.

Each point, including the bomb, is located at some distinct integer location .

You are tasked with identifying the collateral damage inflicted upon the village by outputting the walls that were destroyed.

#### Constraints

Each point is an endpoint of at least one wall, and no two points are the same.

The bomb will not be directly located on any other point or wall.

#### Input Specification

The first line of input contains integers and .

The next lines of input each contain integers and , the coordinates of each point. The points are numbered from to in the order that they were given.

The next lines of input each contain integers and , representing a wall connecting the points numbered and . The walls are numbered from to in the order that they were given.

The next line of input contains another set of integers and , the coordinates of the bomb.

#### Output Specification

Output the indices of the walls that were destroyed in any order (one wall per line).

#### Sample Input 1

27 29
5 1
8 1
9 1
2 2
5 2
8 2
9 2
3 3
5 3
7 3
4 4
5 4
3 6
5 6
7 6
2 7
5 7
1 8
2 8
5 8
7 8
9 8
1 9
2 9
3 9
5 9
7 9
2 1
2 3
5 1
4 5
2 6
6 7
7 3
4 16
16 17
17 20
20 21
21 22
21 27
22 7
5 9
9 8
13 8
14 13
14 12
12 11
14 15
15 10
10 9
18 19
18 23
23 24
24 19
26 25
14 17
4 5

#### Sample Output 1

1
3
4
5
6
8
9
10
11
12
14
16
17
18
21
22
23

#### Explanation for Sample 1

This sample corresponds to the figure above.

#### Sample Input 2

8 8
0 0
6 0
6 8
0 8
2 2
2 4
4 4
4 2
1 2
2 3
3 4
4 1
5 6
6 7
7 8
8 5
3 6

#### Sample Output 2

4
3
2
1