Tin Can Telephone

Interview

Time limit1sMemory limit128 MB

Summary

Count how many polygon buildings touch or cross the straight segment between two windows, where touching a corner or edge blocks the view.

Level: Medium6 of 10
Topics: Geometry, Implementation, Brute force, Math
Solved: No attempts yet

Problem

Romy and Jules have been chatting on their cell phones. Unfortunately, their parents dislike each other and have decided that the two can no longer call each other; in fact, the parents have taken the phones away. So Romy and Jules must find another way to communicate. After searching the web for ideas, they decide to build a "tin can" telephone.

A tin can telephone is simply two empty soup cans joined by a string. To use it, the string is pulled tight; then one person speaks while the other listens. Nothing may touch the string, so that it can vibrate freely and carry sound from one can to the other.

To set up the telephone, Romy and Jules need a clear line of sight between their two bedroom windows. To check whether they can run the string between their rooms, they mark everything on a map that uses integer coordinates. Consider the three situations below.

In these figures, "Romy" is Romy's window at coordinates $(0, 0)$ and "Jules" is Jules' window at coordinates $(3, 3)$ . In the first figure a building stands between the windows and blocks the line of sight. In the second figure the building does not block the view, so the telephone can be set up. In the third figure the straight line from Romy's window to Jules' window would touch a corner of the building; because the string may not touch anything, the view is considered blocked and the telephone cannot be set up.

Input

The first line contains four integers $x_R\ y_R\ x_J\ y_J$ : Romy's window is at $(x_R, y_R)$ and Jules' window is at $(x_J, y_J)$ , where $-1000 \le x_R, x_J \le 1000$ and $-1000 \le y_R, y_J \le 1000$ .

The next line contains a single integer $n$ ( $0 \le n \le 100$ ), the number of buildings. Each of the following $n$ lines describes one building: it begins with an integer giving that building's number of corners, followed by the integer coordinates of those corners listed in either clockwise or counter-clockwise order. No building has more than $32$ corners.

Output

Output a single integer: the number of buildings that touch or block the line of sight between the two windows.

Examples4

Example 1
Input
```
0 0 3 3
1
4 1 2 2 2 2 1 1 1
```
Expected output
```
1
```
Example 2
Input
```
0 0 3 3
0
```
Expected output
```
0
```
Example 3
Input
```
0 0 4 0
1
4 1 -1 3 -1 3 1 1 1
```
Expected output
```
1
```
Example 4
Input
```
0 0 4 0
1
4 1 2 3 2 3 4 1 4
```
Expected output
```
0
```