|
|
Sparing w Programowaniu Zespołowym Politechnika Poznańska, 13.03.2004 |
Zadanie C - Radary |
W Pewnej Wojskowej Krainie (w skrócie: PWK) znajduje się wiele jednostek wojskowych. Każda jednostka reprezentowana jest przez punkt, o współrzędnych całkowitych na płaszczyźnie dwuwymiarowej. Z pewnych bliżej nieokreślonych powodów politycznych, każda jednostka A o współrzędnych (xA,yA) ma za zadanie obserwować wszystkie jednostki B (xB,yB), takie że: xA < xB i yA < yB. Podstawowym narzędziem do obserwacji, używanym przez wszystkie jednostki w PKW, jest radar (tak naprawdę to obserwacji podlega ruch lotniczy wychodzący i wchodzący z/do obserwowanej jednostki, ale nie ma to większego znaczenia w tym zadaniu). Radar działa na takiej zasadzie, że wysyła wiązkę w pewnym konkretnym kierunku (wzdłuż jakiejś półprostej) i analizuje jej odbicie, o ile zaistniało. Ażeby objąć obserwacją większy obszar, radar musi się obracać, nieustannie wysyłając wiązki. Nie chodzi tu jednak o obracanie się w kółko - radar może obracać się w tą i z powrotem, od jednego kąta do drugiego, pokrywając obserwacją pewien wycinek płaszczyzny. Celem jest takie ustawienie radaru (w każdej jednostce) by z jednej strony wszystkie jednostki, które muszą być obserwowane przez daną jednostkę znalazły się w polu jego widzenia, a z drugiej, żeby obserwowany wycinek był jak najmniejszy (żeby radar nie musiał wykonywać zbędnych ruchów).
Mając dane położenie jednostek wojskowych w PKW, należy dla każdej z nich wskazać dwie jednostki, między którymi ma krążyć radar, tak by swoim zasięgiem objął wszystkie te jednostki, które mają być obserwowane z danej. Jeżeli kilka par jednostek spełnia powyższy warunek, to należy wybrać te, które są najbliżej danej jednostki.
W pierwszym wierszu wejścia podana jest dodatnia liczba całkowita D (1 ≤ D ≤ 30), oznaczająca liczbę zestawów testowych, które dalej pojawią się na wejściu. W pierwszym wierszu każdego zestawu danych znajduje się jedna liczba całkowita N (1 ≤ N ≤ 20.000), oznaczająca liczbę jednostek wojskowych w PKW. W kolejnych N wierszach znajdują się pary liczb całkowitych (od 0 do 30.000), będących współrzędnymi jednostek. Nie ma dwóch jednostek o obu takich samych współrzędnych.
Wynik każdego zestawu testowego należy zacząć od wiersza zawierającego "Test x:", gdzie x to numer zestawu (numeracja zaczyna się od 1). Następnie należy wypisać N wierszy, gdzie i-ty wiersz (spośród tych N) opisuje zasięg radaru dla jednostki o numerze i (tzn. dla jednostki pojawiającej się jako i-ta na wejściu). Gdy jednostka ta nie musi w ogóle obserwować żadnej innej, opis ten składa się tylko z liczby –1. W przeciwnym wypadku należy wypisać dwa numery jednostek (możliwie najbliższych jednostce i-tej, w przypadku niejednoznaczności), między którymi ma krążyć radar; należy je wypisać w kierunku przeciwnym do ruchu wskazówek zegara (tzn. najpierw tą jednostkę, że prosta przechodząca przez nią i jednostkę i-tą tworzy mniejszy kąt z osią OX).
2 3 1 1 4 4 3 3 5 0 0 4 1 6 3 1 4 5 6
Test 1: 3 3 -1 2 2 Test 2: 2 4 3 5 -1 5 5 -1