URI Online Judge | 1613

Goemon is in Trouble

By Filipe Nascimento, Universidade de São Paulo - São Carlos BR Brazil

Timelimit: 1

The legendary Ishikawa Goemon will be boiled alive in an iron cauldron if captured! To hide from the guards our hero ran inside a house that contains some walls. It is night and the house is dark, thus the guards threw a light bomb to locate the fugitive. All that is lightened by the explosion will be seen by the guards. The bomb emits infinite light beans, straight, in all directions from its epicenter.

We can simplify this scenario with a 2D cartesian plane, where all walls are segments of the line X = 0. The explosion epicenter will always have its X coordinate with value X < 0. The points where Goemon may hide himself will always have coordinates with X > 0. The image below illustrates the iluminated scenario when the bomb at point E(-12,12) explodes:

The walls are described by line segments, and they block the light. In the above example we have the wall A that goes from point A(0,0) to point A1(0,2), the wall B that goes from B(0,4) to B1(0,6), the wall C that goes from C(0,10) to C1(0,12) and the wall D that goes from D(0,14) to D1(0,16). The epicenter of the explosion is the point E(-12,12) and Goemon may choose to stay at the points G1(8,2), G2(12,14) and G3(10,10). From that three points, he will only be protected at the point G3, because the light beans from the explosion don't hit this point but hit the other points (including point G1), making them visible to the guards.

Given the epicenter of the light explosion, the walls and the points Goemon might stay, compute how many of them are safe for him to hide.


The first line contains an integer T (T = 100) indicating the number of test cases.

In the first line of each case there will be the coordinate (x, y) of the explosion epicenter. The next line will contain an integer P (1 ≤ P*), indicating the number of walls. The next P lines there will be pairs of integers indicating the position of the walls, the start and end of a wall (remember that they stay in the Y axis, it is, X = 0). Then there will be an integer G (G ≤ 100* or G ≤ 104**) indicating the points that are candidates for Goemon to hide. Then G lines will follow with pairs of coordinates (x, y) indicating their coordinates.

All the coordinates will be between -104 and 104 and will be integers. The epicenter of the explosion will have X < 0 and Goemon's positions X > 0. The initial Y of a wall will be strictly less than its end. The walls will not be sorted. The walls won't overlap each other, nor share endpoints. There might be some repeated Goemon positions.

*For around 90% of the cases;

**For the other cases.


For each case output the number of points that are safe for Goemon to stay.

Sample Input Sample Output


-12 12


0 2

4 6

10 12

14 16


8 2

10 10

12 14

-4 -4


10 11

-8 8

20 30


1 0

1 4

1 -4

1 100

1 -100