In the event of technical difficulties with Szkopuł, please contact us via email at szkopul@fri.edu.pl.
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
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.
Napisz program, który:
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:
Twój program powinien wypisać w pierwszym i jedynym wierszu wyjścia jedną liczbę całkowitą: maksymalny stopień jeziora/wyspy.
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.