In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
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.
Today is the day when Professor Byteman - using special laser cannon - is going to contact aliens for the first time in the human history. Unfortunately the sky is thickly covered with clouds. Professor still does not know what the optimal position of the cannon will be, as he cannot yet predict the direction of the wind. Byteman would like to know how many (at maximum) transmission interruptions can the clouds cause (assuming the most pessimistic combination of the position of the laser cannon and the direction of wind).
For the sake of simplicity, let us assume that the clouds in the bytean sky are simple polygons containing their peripheries and that no two different clouds have common points. The wind in Byteland - once it starts blowing, blows constantly in the same direction, causing movement of all clouds in the same direction and with the same velocity. Byteman's laser cannon can be identified with a single point; it emits laser beam constantly straight upwards. A transmission interruption occurs when the laser beam intersects a cloud.
Write a program which:
The first line of the standard input contains one positive integer , denoting the number of clouds in the bytean sky. The following lines contain the description of clouds, each cloud in a separate line. Every description consists of an integer (), denoting the number of sides of the polygon representing the cloud and integers, separated with single spaces and denoting the Cartesian coordinates of the vertices of the polygon. All coordinates are in the range . The total number of vertices of all clouds will be not greater than .
The first and only line of the standard output should contain one integer, representing the maximal possible number of interruptions of Byteman's communication with aliens.
For the input data:
2 5 1 1 5 1 5 4 3 2 1 4 3 2 4 3 5 4 4
the correct result is:
Locating the laser cannon at the point in the case of wind blowing along vector causes 2 transmission interruptions. The maximal number of transmission interruptions (3) can happen for example if the cannon is located at point and the wind blows along vector .
Task authors: Marcin Pilipczuk, Jakub Radoszewski, Piotr Stanczyk.