XI Olimpiada Informatyczna 2003/2004

Zadanie: WYS

Wyspy

Zawody III stopnia, dzien I  
Plik źródłowy: wys.*
Limit pamięci: 32 MB

Bajtocja jest oblana oceanem. Na jej terenie znajdują się jeziora. Na tych jeziorach wyspy, na tych wyspach zdarzają się dalsze jeziorka, a na nich wysepki i tak dalej. Ocean ma stopień zero. Bajtocja, jako wyspa ma stopień 1. Jeziora na wyspach Bajtocji stopień 2, itd., czyli jezioro ma stopień w+1, jeśli znajduje się na wyspie stopnia w, a wyspa ma stopień j+1, jeśli znajduje się na jeziorze stopnia j. Wynika stąd oczywiście, że wszystkie stopnie wysp są nieparzyste, a jezior i oceanu parzyste. Wszystkie jeziora i wyspy mają linie brzegowe w kształcie wielokątów o prostopadłych kolejnych bokach (równoległych do osi układu współrzędnych), a ich wierzchołki mają współrzędne całkowite. Żadne dwie linie brzegowe nie przecinają się, ani nie stykają się. Mając dane kontury linii brzegowych, wyznacz maksymalny stopień wyspy/jeziora w Bajtocji.

Zadanie

Napisz program, który:

Wejście

W pierwszym wierszu wejścia zapisana jest jedna dodatnia liczba całkowita n, liczba linii brzegowych, 1 <= n <= 40000. Linie brzegowe są opisane w kolejnych wierszach, po jednej w wierszu. Każdy z tych wierszy zawiera nieujemne liczby całkowite pooddzielane pojedynczymi odstępami. Pierwsza liczba w wierszu to k, parzysta liczba punktów tworzących linię brzegową, 4 <= k <= 10000. Dalej w wierszu znajduje się k liczb: x1, x2, ..., xk, 0 <= xi <= 108. Kolejne punkty tworzące linię brzegową to: (x1, x2), (x3, x2), (x3, x4), (x5, x4), ... (xk-1, xk), (x1, xk). Są podane we współrzędnych kartezjańskich oraz opisują linię brzegową lewoskrętnie (czyli idąc z punktu i do i+1, wnętrze mamy po lewej stronie). Linie brzegowe są podane w takiej kolejności, że:

Do opisania całej mapy użyto nie więcej niż 200000 punktów.

Wyjście

Twój program powinien wypisać w pierwszym i jedynym wierszu wyjścia jedną liczbę całkowitą: maksymalny stopień jeziora/wyspy.

Przykład

Dla danych wejściowych:

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
poprawnym wynikiem jest:
5