Clouds
Memory limit: 64 MB
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.
Task
Write a program, that:
-
reads from the standard input
the positions, shapes and velocity of the clouds,
-
determines how many times communication is interrupted,
-
writes the result to the standard output.
Input
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.
Output
The first and only line of output should contain exactly one integer:
the number of times the communication is interrupted.
Example
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:
3
The figure shows the clouds seen from above.
The dashed line marks the points that will cross the laser beam.
Task author: Jakub Radoszewski.