Runda 19 [Basic] - Dwa ślimaki

02.05.2011 - Damian Rusak
Trudność


Zadanie tygodnia

runda 19; kategoria Basic

Limit czasowy: 1s; Limit pamięciowy: 32MB


Dwa ślimaki

Dwa ślimaki, Andrzej i Wacław, przyjaźnią się od lat. Zawsze wielką satysfakcję sprawiało im wspólne podróżowanie. Nie da się ukryć, że z powodu ich ślimaczego tempa wspólne wycieczki trwały długo, obaj planowali je więc ze wszystkimi szczegółami.

Ślimaki pełzną po płaszczyźnie. Oznaczyły sobie na niej punkt z którego chcą rozpocząć podróż o współrzędnych ($ x_{s} $, $ y_{s} $) oraz punkt końcowy ($ x_{k} $, $ y_{k} $). Wiadomo, że $ x_{k} $ > $ x_{s} $. Ponadto ślimaki chcą zwiedzić pewną liczbę punktów na płaszczyźnie - tam znajdują się ciekawe atrakcje turystyczne. Każdy z tych punktów ma pewne współrzędne ($ x_{i} $, $ y_{i} $) i wiadomo, że wszystkie punkty (wraz z początkiem i końcem) są różne i zawsze $ x_{s} \leq x_{i} \leq x_{k} $

Ślimaki, choć bardzo się przyjaźnią, nie znoszą spotkań na trasie - uważają, że lepiej zobaczyć się na końcu i opowiedzieć sobie o wszystkich zaznanych przygodach przy kawałku dobrego liścia. Zatem oba wyruszają z początkowego punktu, oba mają skończyć w punkcie końcowym, ale poza nimi ich trasy nie mogą się przecinać ani mieć punktów wspólnych. Ślimaki zawsze podróżują po linii prostej od jednej atrakcji do kolejnej (podobnie z punktem początkowym i końcowym). Chcą, aby ich trasy zawarły w sobie wszystkie atrkacje turystyczne. Czy pomożesz im wyznaczyć taką trasę??

Wejście:

Pierwsza linia wejścia zawiera jedną liczbę całkowitą $ n $ - liczbę atrkacji turystycznych ($ 1 \leq n \leq 10^{6} $). W kolejnej linii znajdują się liczby całkowite $ x_{s} $, $ y_{s} $$ x_{k} $, $ y_{k} $. (wszystkie z zakresu $ \left[0,10^{9}\right] $). W kolejnych $ n $ liniach znajdują się współrzędne ($ x_{i} $, $ y_{i} $) kolejnych atrakcji turystycznych, podane w kolejności rosnącej współrzędnej $ x $. (z zakresu $ \left[0,10^{9}\right] $).

Wyjście:

Wyjście powinno składać się z dwóch linii - pierwsza powinna zawierać numery atrakcji turystycznych w kolejności, w jakiej zwiedzać będzie je pierwszy ślimak, druga zaś numery zwiedzane przez drugiego ślimaka. Jeśli istnieje wiele rozwiązań, Twój program może wypisać dowolne z nich. Atrakcje numerowane są od $ 1 $ do $ n $.

Przykład:

Wejście:

3
0 0 7 2
2 2
3 1
6 4

Wyjście:

1 3
2

Pierwszy ślimak pełznie od (0,0) do (2,2), potem do (6,4), wreszcie do (7,2). Drugi ślimak porusza się od (0,0) do (3,1), potem do (7,2). Trasy nie przecinają się ani nie posiadają punktów wspólnych poza początkiem i końcem.

 

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
4
Twoja ocena: Brak Ocena: 4 (2 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com