In the event of technical difficulties with Szkopuł, please contact us via email at szkopul@fri.edu.pl.
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
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 p-odcinków,
z których każde kolejne dwa są prostopadłe,
nazywamy po-łamaną stopnia
.
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 i
tego p-punktu.
Liczby te należą do przedziału
.
W pierwszym wierszu standardowego wejścia znajduje się
tylko opis p-punktu
.
W drugim wierszu znajduje się tylko opis p-punktu
.
W trzecim wierszu zapisana jest dokładnie jedna nieujemna liczba
całkowita
będąca liczbą p-odcinków,
.
W każdym z kolejnych
wierszy znajdują się
opisy ydokł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 standardowego wyjścia
powinna znaleźć się jedna liczba będąca minimalnym stopniem
po-łamanej łączącej punkty i
oraz nie przecinającej
żadnego z zadanych p-odcinków, lub słowo "BRAK",
jeśli po-łamana o powyższych własnościach nie istnieje.
Dla danych wejściowych:
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:
5
Autor zadania: Grzegorz Jakacki.