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.
We have a polygon chosen in the cartesian coordinate system. Sides of the polygon are parallel to the axes of coordinates. Every two consecutive sides are perpendicular and coordinates of every vertex are integers. We have also given a window that is a rectangle whose sides are parallel to the axes of coordinates. The interior of the polygon (but not its periphery) is coloured red. What is the number of separate red fragments of the polygon that can be seen through the window?
Look at the figure below:
There are two separate fragments of the polygon that can be seen through the window.
Write a program that:
In the first line of the standard input there are four integers from the range , separated by single spaces. The numbers are the coordinates of the top-left corner of the window. The numbers are the coordinates of the bottom-right corner of the window.
The next line of the input file contains one integer , , which equals the number of vertices of the polygon. In the following lines there are coordinates of polygon's vertices given in anticlockwise direction, i.e. the interior of the polygon is on the left side of its periphery when we move along the sides of the polygon according to the given order. Each line contains two integers separated by a single space, , . The numbers in the -nd line, , are coordinates of the -th vertex of the polygon.
In the first and only line of the standard input there should be one integer — the number of separate red fragments of the polygon that can be seen through the window.
For the input data:
0 5 8 1 24 0 0 4 0 4 2 5 2 5 0 7 0 7 3 3 3 3 2 2 2 2 4 1 4 1 5 2 5 2 6 3 6 3 5 4 5 4 6 5 6 5 4 7 4 7 7 0 7
the correct result is:
Task author: Wojciech Guzicki.