In the event of technical difficulties with Szkopuł, please contact us via email at firstname.lastname@example.org.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
There are clouds in the sky, all moving continuously with a wind in the same direction and with the same constant velocity , i.e. for any real number and any point of a cloud with initial coordinates the position of this point at time is .
For the sake of simplicity, we assume that every cloud is a polygon (containing its periphery), whose vertices have integer coordinates. This polygon does not have to be convex, but no two of its edges cross each other (with exception of the common endpoints of consecutive edges). The clouds may intersect.
On the ground there is a satellite control center, at coordinates , and there is a satellite directly above the control center and above the clouds. Straight upwards from the control center to the satellite goes a laser beam. The laser beam is used to communicate with the satellite. However, when the beam crosses a cloud, the communication is not possible. Initially, the beam does not cross any cloud. During the observation, there may be several moments, when the laser beam crosses (one or more) clouds, interrupting the communication. Even when the laser beam crosses a single vertex of a cloud, the communication is interrupted for an instant. You are to write a program that computes how many times the communication is interrupted, until all the clouds drift away.
Write a program, that:
The first line of input contains three integers and , separated by single spaces, , ; is the number of clouds, is the velocity vector of the clouds (). The x-coordinates correspond to the West-East direction and the y-coordinates correspond to the North-South direction.
The following lines contain descriptions of the clouds, one cloud per line. Each of these lines consists of a sequence of integers, separated by single spaces. The first integer in a line is the number of cloud's vertices , . It is followed by integers: , ; are the coordinates of the consecutive vertices in a clockwise order.
The laser beam crosses clouds peripheries at most times.
The first and only line of output should contain exactly one integer: the number of times the communication is interrupted.
For the input data:
4 -2 -1 4 6 2 6 4 8 4 8 2 4 2 3 1 -1 2 5 4 2 3 -3 1 -1 2 -1 -1 5 5 3 3 3 3 5 6 5 6 -1
the correct result is:
The figure shows the clouds seen from above. The dashed line marks the points that will cross the laser beam.
Task author: Jakub Radoszewski.