English
Zobacz więcej:
- dla uczniów szkół podstawowych: oij.edu.pl/start/
- dla uczniów szkół średnich: oi.edu.pl/l/jak_zaczac/
Zadanie Wyspy (wys)
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.
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.