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.
A skating competition was organized on the largest icerink in Byteland. The icerink is a square of size . A competitor begins skating at the START point chosen by referees and his task is to finish sliding at the FINISH point, also chosen by referees. The points of START and FINISH are different. One can slide in directions parallel to the sides of the icerink. There are some obstacles placed on the icerink. Each obstacle is a prism, which base is a polygon with sides parallel to the sides of the icerink. Each two adjacent sides of the base are always perpendicular. The obstacles do not have common points. Each slide finishes up at the point where a competitor, for the first time, meets the wall of an obstacle, which is perpendicular to the direction of the slide. In other words, one can stop only when he crashes on a wall or in the FINISH point. Falling out of the icerink causes disqualification. Competitor may slide along walls of an obstacle.
Decide, whether a competitor who slides according to the given rules may reach the finish point, assuming he begun sliding from the starting point. If so, what is the minimal number of slides he needs to do?
Write a program which:
We define a system of coordinates to describe positions of objects on a rink. The rink is a square with vertices , , , . In the first line of standard input there are two integers and separated by a single space, . The pair denotes coordinates of the START point. In the second line of the file there are two integers and separated by single space, . The pair denotes coordinates of the FINISH point. The third line of the file contains one integer , . This is the number of obstacles. The following lines comprise descriptions of obstacles. Each description of an obstacle begins with the line containing one positive integer equal to the number of walls (sides of the base) of the obstacle. In each of the following lines there are two integers and separated by a single space. These are the coordinates of the vertices of the obstacle's base, given in a clockwise order. (i.e. when going around the obstacle in this direction the inside is on the left-hand side). The total number of side walls of the obstacles does not exceed .
Your program should write in the only line of the standard output:
For the input data:
40 10 5 40 3 6 0 15 0 60 20 60 20 55 5 55 5 15 12 30 55 30 60 60 60 60 0 0 0 0 5 55 5 55 35 50 35 50 40 55 40 55 55 6 30 25 15 25 15 30 35 30 35 15 30 15
describing the following configuration of obstacles:
the correct result is:
These are possible sequences of slides of length 4:
Task author: Marcin Kubica.