Lodowisko

Limit pamięci: 32 MB

Na największym lodowisku w Bajtocji zorganizowano zawody w ślizganiu. Lodowisko ma kształt kwadratu o rozmiarach . Zawodnik rozpoczyna ślizgi z punktu startowego wskazanego przez sędziów i ma za zadanie zakończyć ślizgi w punkcie docelowym, również wskazanym przez sędziów. Punkty startowy i docelowy są różne. Ślizgi mogą odbywać się tylko w kierunkach równoległych do boków lodowiska. Na lodowisku rozstawiono przeszkody. Każda przeszkoda jest graniastosłupem, którego podstawy są wielokątami o bokach równoległych do boków lodowiska. Każde dwa kolejne boki podstawy są zawsze do siebie prostopadłe. Przeszkody nie mają wspólnych punktów. Każdy ślizg kończy się przy pierwszym zetknięciu ze ścianą pewnej przeszkody, która to ściana jest prostopadła do kierunku ślizgu i ogranicza wnętrze przeszkody w kierunku tego ślizgu. Innymi słowy, zatrzymanie następuje wyłącznie na ścianie, na którą się "wpada" lub w punkcie docelowym. Wypadnięcie z lodowiska oznacza dyskwalifikację. Ślizgi mogą odbywać się wzdłuż ściany przeszkody.

Czy zawodnik wykonujący ślizgi zgodnie z podanymi regułami może dotrzeć z punktu startowego do punktu docelowego? Jeśli tak, to jaka jest najmniejsza liczba ślizgów, które musi wykonać?

Zadanie

Napisz program, który:

• wczytuje ze standardowego wejścia opis lodowiska i przeszkód oraz współrzędne punktów startowego i docelowego,
• sprawdza, czy ślizgając się można z punktu startowego dotrzeć do punktu docelowego, a jeżeli tak, to oblicza najmniejszą liczbę ślizgów potrzebną do tego,
• wypisuje wynik na standardowe wyjście.

Wejście

Plan lodowiska jest naniesiony na siatkę prostokątną o rozmiarach . Dolny lewy róg siatki ma współrzędne . Górny prawy róg siatki ma współrzędne . W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite i oddzielone pojedynczym odstępem, . Para to współrzędne punktu startowego. W drugim wierszu wejścia znajdują się dwie liczby całkowite i oddzielone pojedynczym odstępem, . Para to współrzędne punktu docelowego. Trzeci wiersz wejścia zawiera jedną liczbę naturalną , . Jest to liczba przeszkód. Kolejne wiersze zawierają opisy przeszkód. Każdy opis przeszkody rozpoczyna się od wiersza zawierającego jedną dodatnią liczbę całkowitą równą liczbie ścian bocznych (boków podstawy) przeszkody. W kolejnych wierszach znajdują się po dwie liczby całkowite i oddzielone pojedynczym odstępem. Są to kolejne współrzędne wierzchołków podstawy przeszkody przy obchodzeniu jej zgodnie z ruchem wskazówek zegara (tzn. przy obchodzeniu przeszkody wnętrze znajduje się zawsze po prawej stronie obchodzącego). Łączna liczba ścian bocznych w przeszkodach nie przekracza .

Wyjście

Twój program powinien zapisać w jednym wierszu standardowego wyjścia:

• jedno słowo NIE, gdy nie jest możliwe dotarcie z punktu startowego do punktu docelowego
• albo najmniejszą liczbę ślizgów potrzebną w tym celu, w przeciwnym przypadku.

Przykład

Dla danych wejściowych:

40 10
5 40
3
6
0 15
0 60
20 60
20 55
5 55
5 15
12
30 55
30 60
60 60
60 0
0 0
0 5
55 5
55 35
50 35
50 40
55 40
55 55
6
30 25
15 25
15 30
35 30
35 15
30 15

opisujących następujący układ przeszkód:

poprawną odpowiedzią jest:

4

Oto możliwe ciągi ślizgów długości 4:

Autor zadania: Marcin Kubica.