## CEOI '14 P2 - Fangorn

View as PDF

Points: 20 (partial)
Time limit: 1.4s
Memory limit: 64M

Problem type
##### The Forest of Fangorn

Since entering Fangorn Forest, Gimli the dwarf feels uncomfortable. There is something wrong with the trees here! Therefore, Gimli wants to reach one of the camps at the edge of the forest. However, in order to feel safe, at any time Gimli needs to see all trees. Fortunately, dwarves have very good eyes: they can see infinitely far and into every direction.

Fangorn Forest forms a rectangle , with sides parallel to the axes of the coordinate system, and with corners at points and . All trees in the forest lie in the interior of , and all camps (numbered from to ) lie on the sides of . Any tree grows straight upwards ("out of the map"), and can be considered a point. Thus, Gimli sees a tree from his position if and only if no other tree lies on the line segment connecting his position and the tree.

From any camp Gimli can see all trees. At the beginning he is located in the interior of the forest, but not on a tree's position (dwarves do not climb trees), and he can see all camps and all trees. Since the Forest of Fangorn is very old, there are no three trees lying on a common line.

Gimli can safely reach a camp , if there is a path from his original position to such that from any point of he can see all trees. Help Gimli by writing a program that finds all the camps he can safely reach.

#### Input Specification

The first line contains two integers and that indicate the size of the rectangle , as described above. The second line contains two integers and , the coordinates of Gimli's initial position.

The third line contains an integer , the number of camps. The following lines describe the camps; the of these lines contains two integers and , the coordinates of camp number .

The line after that contains an integer , the number of trees. The following lines describe the trees; each of these lines contain two integers and , the coordinates of a tree. No two of these lines are identical.

#### Output Specification

The first line should contain the number of camps Gimli can safely reach. If , the next line should contain the numbers of these camps in increasing order.

For all testcases , , and .

Subtask 2 20% The trees form the corners of a convex polygon and

#### Sample Input 1

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

#### Sample Output 1

2
1 3

#### Explanation for Sample Output 1

The situation of the first testcase together with possible paths from Gimli's starting position to the (safely) reachable camps:

Note that Gimli is allowed to leave the forest during his path. However, even outside the forest he must see all trees—otherwise he would be able to reach the second camp, too.

#### Sample Input 2

9 4
1 2
1
8 4
4
1 1
6 1
3 3
4 3

#### Sample Output 2

0