![]() |
||
Grzegorz Jakacki (treść) Marcin Mucha (opracowanie, program wzorcowy) Po-łamanaW 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. ZadanieNapisz program, który:
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..1 000 000 000]. 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, WyjścieW pierwszym i jedynym wierszu pliku tekstowego POL.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śli po-łamana o powyższych własnościach nie istnieje. \openin\tmpfile testdir.inp \ifeof\tmpfile \write16SINOL: brak pliku 'testdir.inp' \else \read\tmpfile to\sinolTestIn \ifeof\tmpfile \write16SINOL: plik 'testdir.inp' skonczyl sie zbyt wczesnie \else \read\tmpfile to\sinolTestOut \fi \fi \closein\tmpfile PrzykładDla 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 Rozwiązanie wzorcoweNiech x_1 < x_2 < ... będzie rosnąco uporządkowanym ciągiem (bez powtórzeń) współrzędnych x wszystkich końców odcinków z dodatkowo dodaną współrzędną x punktu B. Niech y_1 < y_2 < ... będzie analogicznym ciągiem dla współrzędnej y. Rozważmy podział osi ![]()
Rys. 1. Podział płaszczyzny dla przykładowego zestawu p-odcinków ![]() Niech P1 i P2 będą dwoma elementami powyższego podziału. Jeśli z pewnego punktu Oznacza to, że punkty w jednym elemencie podziału zachowują się identycznie, jeśli chodzi o istnienie łamanych o końcu w punkcie B. Rozwiązanie w zasadzie się narzuca. Trzeba skonstruować graf, w którym wierzchołkami są elementy podziału (ma on strukturę kraty, co ułatwia implementację), krawędzie zaś oznaczają możliwość przejścia z jednego elementu do innego. Następnie w tym grafie używamy procedury przeszukiwania wszerz (BFS), aby znaleźć łamaną minimalnego stopnia łączącą element zawierający punkt A z punktem B. Musimy jednak w procedurze BFS dokonać dwu modyfikacji:
TestyDo sprawdzenia rozwiązań zawodników użyto 12 testów: |