Chmury [A]
Limit pamięci: 64 MB
Co za pech!
Właśnie dzisiaj Profesor Bajtazar postanowił za pomocą specjalnego działka
laserowego nawiązać pierwszy w historii ludzkości kontakt z kosmitami,
lecz niestety niebo jest gęsto pokryte chmurami.
Profesor nie wie jeszcze, w którym dokładnie miejscu najlepiej będzie
postawić działko, nie jest on w stanie przewidzieć również, w którą stronę
powieje wiatr.
Bajtazar zastanawia się, ile maksymalnie przerw w transmisji komunikatów
w kosmos mogą spowodować chmury (przy najbardziej pesymistycznej kombinacji
ustawienia działka i kierunku wiatru).
Dla uproszczenia załóżmy, że chmury znajdujące się na bajtockim niebie
mają kształt wielokątów prostych, zawierających brzeg
oraz że żadne dwie różne chmury nie mają wspólnych punktów.
Wiatr w Bajtocji, jak już zaczyna wiać, to wieje cały czas w tym samym
kierunku i powoduje przemieszczanie się wszystkich chmur z tym samym wektorem
prędkości.
Działko Bajtazara można utożsamiać z jednym punktem; emituje ono
promieniowanie laserowe nieprzerwanie pionowo do góry.
Przerwa w transmisji następuje wtedy, kiedy promień lasera jest
przysłonięty przez jakąś chmurę.
Zadanie
Napisz program, który:
- wczyta ze standardowego wejścia opis ułożenia chmur
na bajtockim niebie,
- wyznaczy maksymalną możliwą liczbę przerw w komunikacji z kosmitami,
jakie mogą się przydarzyć Profesorowi Bajtazarowi,
- wypisze wynik na standardowe wyjście.
Wejście
Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą dodatnią ,
oznaczającą liczbę chmur na bajtockim niebie.
Kolejne wierszy zawiera opisy chmur, po jednym w wierszu.
Każdy z nich składa się z liczby całkowitej (),
oznaczającej liczbę boków wielokąta reprezentującego chmurę
oraz z liczb całkowitych, pooddzielanych pojedynczymi
odstępami i oznaczających współrzędne kartezjańskie wierzchołków
wielokąta na niebie.
Wszystkie współrzędne będą należeć do przedziału .
Łączna liczba wierzchołków chmur będzie niewiększa niż .
Wyjście
Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbą
całkowitą, oznaczającą maksymalną możliwą liczbę przerw w kominikacji
Bajtazara z kosmitami.
Przykład
Dla danych wejściowych:
2
5 1 1 5 1 5 4 3 2 1 4
3 2 4 3 5 4 4
poprawną odpowiedzią jest:
3
W przypadku umieszczenia lasera w punkcie i wiatru wiejącego
w kierunku wektora nastąpiłyby 2 przerwy w transmisji.
Maksymalna liczba przerw w transmisji (3) może się przydarzyć na przykład
wtedy, gdy działko zostanie umieszczone w punkcie , a wiatr
będzie wiał w kierunku wektora .
Autorzy zadania: Marcin Pilipczuk, Jakub Radoszewski, Piotr Stańczyk.