Wyspy
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ń
, jeśli znajduje się na wyspie stopnia , a wyspa ma stopień
, jeśli znajduje się na jeziorze stopnia .
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:
-
wczyta ze standardowego wejścia opisy linii brzegowych wysp i
jezior,
-
obliczy maksymalny stopień jeziora/wyspy,
-
wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu wejścia zapisana jest jedna dodatnia liczba
całkowita , liczba linii brzegowych, .
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 , parzysta liczba punktów
tworzących linię brzegową, .
Dalej w wierszu znajduje się liczb: ,
.
Kolejne punkty tworzące linię brzegową
to: , , , ,
..., , .
Są podane we współrzędnych kartezjańskich oraz opisują
linię brzegową lewoskrętnie (czyli idąc z punktu do ,
wnętrze mamy po lewej stronie).
Linie brzegowe są podane w takiej kolejności, że:
-
linia brzegowa każdego jeziora jest podana zawsze po
linii brzegowej wyspy, na której się znajduje,
-
linia brzegowa każdej wyspy jest podana zawsze po linii
brzegowej jeziora, na którym się znajduje.
Do opisania całej mapy użyto nie więcej niż
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
4 4 6 7 9
4 6 8 5 7
6 10 9 15 10 9 7
poprawną odpowiedzią jest:
5
Autor zadania: Piotr Chrząstowski.