Zadanie 5 - Szachownica
Jest szachownica n na n. Chcemy na niej postawić n wież tak, żeby żadne dwie
się nie biły. Ponadto każda wieża ma wyznaczony prostokąt, w którym ma się
znajdować.
Wejście
W pierwszym wierszu standardowego wejścia znajduje się jedna liczba
całkowita N (1<=N<=500000) - rozmiar szachownicy. W kolejnych N
liniach znajdują się po cztery liczby całkowite
xpi,
ypi,
xki,
yki pomiędzy 1 i N włącznie. Oznaczają one, że współrzędne wieży
numer i muszą spełniać warunki:
xpi<=xi<=xki oraz
ypi<=yi<=yki.
Wyjście
Na standardowe wyjście wypisz N wierszy, w każdym po dwie liczby od 1 do N.
Będą to współrzędne x, y wieży numer i. Wybierz dowolne z możliwych
ustawień. Załóż, że jakieś istnieje.
Przykład
Dla wejścia:
4
1 1 4 4
2 2 3 3
2 2 3 3
1 4 1 4
poprawnym wyjściem jest na przykład:
4 1
2 3
3 2
1 4
Wersja prostsza
Załóż, że wszystkie yp są równe 1, a wszystkie yk są równe N. (Jest to
jednocześnie wskazówka do wersji podstawowej.)
Jak ktoś chce może rozwiązać tylko prostszą wersję. Rozwiązania należy wysyłać na adres: parys@mimuw.edu.pl do godziny 17:00 dnia
9.XII.2004 (pierwszy termin 2.XII.2004).