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.
Byteotia is an island surrounded by ocean. There are lakes in Byteotia. On these lakes there are isles which themselves contain lakes on which in turn there are further isles and so on. The ocean has degree . Byteotia has degree . The lakes situated on the Byteotian Isles have degree etc., so a lake has degree if it is situated on an island of degree and and island has a degree if it lies on a lake of degree . It follows that the degrees of all islands are odd whereas the degrees of lakes and the ocean are always even. All lakes and islands have coastlines in shape of polygons whose each edge is perpendicular to its neighbours (the edges are parallel to the axes , ) and their vertices have integer coordinates. No two coastlines meet or intersect. Having been given the contours of the coastlines calculate the maximum degree of lake/island in Byteotia.
Write a programme which:
In the first line there is one integer , the number of coastlines, . The coastlines are described in the following lines, a single coastline per line. Each of the lines contains non-negative integers separated by single spaces. The first number in each line, , signifies the even number of points comprising the coastline, . Next there are numbers: , . The points forming the coastline are . They are given in the cartesian coordinates and anticlockwise (so while going from to we always have the interior on the left side). The coastlines are given in such order that:
To describe the whole map no more than points have been used.
Your programme should write in the first and only line a single integer - the maximum degree of island/lake.
For the input data:
6 4 1 0 17 12 16 10 4 16 11 2 4 8 2 3 3 2 1 16 3 15 2 8 8 10 3 5 12 8 11 6 6 10 9 15 10 9 7 4 4 6 7 9 4 6 8 5 7
the correct result is:
Task author: Piotr Chrzastowski.