Polish version    English version  
  Historia OI -> VII OI 1999/2000 -> 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
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
Zadania
Regulamin
Zasady organizacji
Wskazówki
Terminarz
Statystyki
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
VII Olimpiada Informatyczna 1999/2000

Zadanie: POL
Autor: Grzegorz Jakacki
Po-lamana

Zawody III stopnia, dzień pierwszy 12 kwietnia 2000
Plik źródłowy: POL.??? (np. pas, c, cpp)
Plik wykonywalny: POL.exe
Plik wejściowy: POL.in
Plik wyjściowy: POL.out

W prostokątnym układzie współrzędnych każdy punkt o współrzędnych całkowitych nazywamy p-punktem. Dowolny odcinek równoległy do jednej z osi współrzędnych, o różnych końcach będących p-punktami, nazywamy p-odcinkiem. Rozważamy odcinki domknięte, tzn. końce należą do odcinka. Łamaną zbudowaną z k p-odcinków, z których każde kolejne dwa są prostopadłe, nazywamy po-łamaną stopnia k.

Zadanie

Napisz program, który:

  • wczyta z pliku tekstowego POL.IN opisy pewnej liczby p-odcinków oraz współrzędne dwóch różnych p-punktów A i B,
  • wyznaczy minimalny stopień po-łamanej łączącej te dwa punkty i nie przecinającej żadnego z danych p-odcinków lub stwierdzi, że taka po-łamana nie istnieje,
  • zapisze wynik do pliku tekstowego POL.OUT.

Wejście

Opis p-punktu składa się z dwóch nieujemnych liczb całkowitych oddzielonych pojedynczym odstępem, będących odpowiednio współrzędnymi x i y tego p-punktu. Liczby te należą do przedziału [0..1000000000]. W pierwszym wierszu pliku wejściowego POL.IN znajduje się tylko opis p-punktu A. W drugim wierszu znajduje się tylko opis p-punktu B. W trzecim wierszu zapisana jest dokładnie jedna nieujemna liczba całkowita n będąca liczbą p-odcinków, 1<=n<=50. W każdym z kolejnych n wierszy znajdują się opisy dokładnie dwóch p-punktów, oddzielone pojedynczym odstępem. Są to współrzędne końców jednego p-odcinka.

Wyjście

W pierwszym i jedynym wierszu pliku tekstowego LOL.OUT powinna znaleźć się jedna liczba będąca minimalnym stopniem po-łamanej łączącej punkty A i B oraz nie przecinającej żadnego z zadanych p-odcinków, lub słowo BRAK, je"sli po-łamana o powyższych własnościach nie istnieje.

Przykład

Dla pliku wejściowego POL.IN:

1 2
3 4
5
0 0 7 0
0 5 7 5
2 2 2 7
4 0 4 3
3 2 6 2

poprawną odpowiedzią jest plik wyjściowy POL.OUT:

5



Wersja do druku