Polish version    English version  
  Historia OI -> XI OI 2003/2004 -> Zadania


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
Terminarz
Zadania
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
II Etap
III Etap
Przepisy
Dla zawodnikow
Przydatne zasoby
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
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:

  • 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 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:

  • 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ż 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



Wersja do druku