VII Olimpiada Informatyczna 1999/2000
|
Zadanie: POL
|
Autor: Grzegorz Jakacki
|
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.
Napisz program, który:
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.
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.
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