Skoczki
Limit pamięci: 32 MB
Skoczek porusza się po nieskończonej szachownicy.
Każdy z ruchów, jakie może wykonać skoczek, można opisać
parą liczb całkowitych - para odpowiada
możliwości wykonania ruchu z pola o współrzędnych
na pole lub .
Dla każdego skoczka określony jest zestaw takich par,
opisujących ruchy jakie może wykonywać skoczek.
Zakładamy, że wszystkie pola, na które może ruszyć się skoczek
z pola nie leżą na jednej prostej.
Powiemy, że dwa skoczki są równoważne, jeżeli dla
obu skoczków zbiory pól, do jakich mogą dotrzeć z
pola (być może w wielu ruchach) są takie same.
(Przy czym równoważne skoczki mogą docierać do tych
pół w różnych liczbach kroków).
Można pokazać, że dla każdego skoczka istnieje
równoważny mu skoczek, którego ruchy są opisane za pomocą tylko
dwóch par liczb.
Zadanie
Twoje zadanie polega na napisaniu programu, który:
-
wczyta ze standardowego wejścia pary liczb całkowitych
opisujące ruchy skoczka,
-
wyznaczy dwie pary liczb całkowitych opisujące skoczka
równoważnego danemu skoczkowi,
-
wypisze wyznaczone dwie pary liczb na standardowe wyjście.
Wejście
W pierwszym wierszu standardowego wejścia
zapisana jest jedna liczba całkowita , liczba par liczb
opisujących ruchy danego skoczka, .
W kolejnych wierszach zapisane są pary liczb opisujące ruchy
danego skoczka, po jednej w wierszu.
W każdym z tych wierszy zapisane są po dwie liczby całkowite
i oddzielone pojedynczym odstępem,
.
Zakładamy, że
Wyjście
W pierwszym wierszu standardowego wyjścia
należy wypisać dwie liczby całkowite i
oddzielone pojedynczym odstępem, .
W drugim wierszu należy zapisać dwie liczby całkowite i
oddzielone pojedynczym odstępem, .
Powinny to być takie liczby całkowite, że skoczek, którego
ruchy są opisane parami i jest równoważny skoczkowi
opisanemu w danych wejściowych.
Przykład
Dla danych wejściowych:
3
24 28
15 50
12 21
poprawne wyjście może mieć np. postać:
468 1561
2805 9356
lub:
3 0
0 1
Autor zadania: Wojciech Guzicki.