ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural SU contest. Petrozavodsk training camp. Summer 2010

About     Problems     Submit solution     Judge status     Standings
Contest is over

H. Fly Hunt

Time limit: 2.0 second
Memory limit: 64 MB
Pakhom and his friends decided to hunt for flies. Each of them took his favourite fly swatter. They crouched to a wall with n careless flies sitting on it and simultaneously swatted the wall so that each swatter left a mark on it. The mark of each swatter is a simple polygon with interior. No two swatter marks have common points. A fly was killed if it was situated inside or on the border of a swatter mark. Help friends calculate a number of flies killed by each of them.


The first line contains a number of flies n (1 ≤ n ≤ 105). The next n lines contain coordinates of the flies. No two flies are situated at the same point. The next line contains a number of fly swatters m (1 ≤ m ≤ 30 000). Each of the next m lines describes a mark of a fly swatter. A mark is described by a number of vertices in a corresponding polygon and coordinates of these vertices in counter-clockwise order. The total number of vertices in all polygons doesn't exceed 105. All coordinates are integers and don't exceed 107 in their absolute value. All numbers in lines are separated by single spaces.


Output the number of flies killed by each fly swatter. Describe the fly swatters in the order they are given in the input.


0 0
1 1
4 4
3 -2 -2 -3 -3 -2 -3
3 0 0 2 0 1 1
3 3 0 5 0 4 6
Problem Author: Denis Dublennykh
Problem Source: Ural SU Contest. Petrozavodsk Summer Session, August 2010
To submit the solution for this problem go to the Problem set: 1848. Fly Hunt