COCI '16 Contest 3 #6 Meksikanac

View as PDF

Submit solution


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

Problem types

Do you know what is the difference between a hotel and a motel? That's right, the difference is in the number of flies that live there. Norman is an owner of one of the more popular American motels, but his mother insists he turns it into a hotel. That's exactly why Norman got a flyswatter (a fly-killing device) in the shape of a polygon with K edges as a Christmas present in 2016.

Wanting to meet his mother's demands, Norman found himself in front of a window with N flies. Since Norman wouldn't even harm a fly, he wants to know how many ways there are for him to hit the window with the flyswatter, without harming a single fly.

The window is a rectangle with its lower left vertex placed in the center of the coordinate system. After Norman's blow to the window, the vertices of the polygon must lie on integer coordinates, and the flyswatter must be located within the window with all its area. A fly is considered hurt if it's located on the vertex, edge or within the flyswatter.

Input Specification

The first line of input contains integers X_p, Y_p and N (1 \le X_p, Y_p \le 500, 0 \le N \le X_p \times Y_p), the coordinates of the upper right corner of the window and the number of flies on the window, respectively.

Each of the following N lines contains two integers X and Y (0 < X < X_p, 0 < Y < Y_p), the coordinates of a fly on the window.

The following line contains the integer K (3 \le K \le 10\,000), the number of vertices of the flyswatter.

Each of the following K lines contains two integers X_i, Y_i (-10^9 \le X_i, Y_i \le 10^9), the i^\text{th} vertex of the flyswatter. The flyswatter vertices are provided in order of joining lines, so neighbouring vertices are connected by a straight line.

Output Specification

You must output how many ways there are for Norman to hit the window with the flyswatter, without harming a single fly.

Scoring

In test cases worth 62.5\% of total points, it will hold 1 \le X_p, Y_p \le 100.

Sample Input 1

4 5 2
1 3
3 4
4
0 0
2 0
2 2
0 2

Sample Output 1

4

Sample Input 2

5 5 3
1 4
1 3
2 2
3
4 7
6 3
7 6

Sample Output 2

3

Sample Input 3

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

Sample Output 3

1

Explanation for Sample Output 3


Comments

There are no comments at the moment.