Polish version    English version  
  Historia OI -> VI OI 1998/1999 -> 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
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
Zadania
Regulamin
Zasady organizacji
Wskazówki
Terminarz
Statystyki
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
VI Olimpiada Informatyczna 1998/99

Zadanie: LOD
Autor: Marcin Kubica
Lodowisko

Zawody II stopnia, dzień drugi 11 lutego 1999
Plik źródłowy: LOD.??? (np. pas, c, cpp)
Plik wykonywalny: LOD.exe
Plik wejściowy: LOD.in
Plik wyjściowy: LOD.out

Na największym lodowisku w Bajtocji zorganizowano zawody w ślizganiu. Lodowisko ma kształt kwadratu o rozmiarach 10000 10000. 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 z pliku tekstowego LOD.IN 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,
  • zapisuje wynik w pliku tekstowym .

Wejście

Plan lodowiska jest naniesiony na siatkę prostokątną o rozmiarach 10000*10000. Dolny lewy róg siatki ma współrzędne (0,0). Górny prawy róg siatki ma współrzędne (10000,10000). W pierwszym wierszu pliku wejściowego LOD.IN znajdują się dwie liczby całkowite z1 i z2 oddzielone pojedynczym odstępem, 0<=z1, z2<=10000. Para (z1, z2) to współrzędne punktu startowego. W drugim wierszu pliku LOD.IN znajdują się dwie liczby całkowite t1 i t2 oddzielone pojedynczym odstępem, 0<=t1, t2<=10000. Para (t1, t2) to współrzędne punktu docelowego. Trzeci wiersz pliku LOD.IN zawiera jedną liczbę naturalną s, 1<=s<=2500. Jest to liczba przeszkód. Kolejne wiersze zawierają opisy s przeszkód. Każdy opis przeszkody rozpoczyna się od wiersza zawierającego jedną dodatnią liczbę całkowitą r równą liczbie ścian bocznych (boków podstawy) przeszkody. W kolejnych r wierszach znajdują się po dwie liczby całkowite x i y 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 10000.

Wyjście

Twój program powinien zapisać w jednym wierszu pliku wyjściowego : itemize jedno słowo 'NIE', gdy nie jest możliwe dotarcie z punktu startowego do punktu docelowego lub najmniejszą liczbę ślizgów potrzebną w tym celu, w przeciwnym przypadku. itemize

Przykład

Dla pliku wejściowego LOD.IN:

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ącego następujący układ przeszkód:

poprawną odpowiedzią jest plik tekstowy LOD.OUT:

4

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




Wersja do druku