Runda 23 [Hard] - Duchy

13.06.2011 - Damian Rusak

Zadanie tygodnia

runda 23; kategoria Hard

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

Duchy

Na dalekich bagnach straszą duchy. Wbrew pozorom duchy to bardzo towarzyskie osoby - uwielbiają swoje towarzystwo i wspólne gry pośród gęstych wyziewów torfowisk. Duchy szczególnie upodobały sobie grę w kwadraty.

Możemy dla uproszczenia myśleć o duchach jak o punktach na płaszczyźnie. Gra polega na tym, że wszystkie duchy poza jednym stoją w miejscu, a ten jeden musi ustawić tak, aby tworzył kwadrat z choć jednym innym duchem. Przez "tworzenie" kwadratu rozumiemy tu sytuację w której punkty reprezentujące te dwa duchy są przeciwległymi wierzchołkami pewnego kwadratu o bokach równoległych do osi układu współrzędnych.

Czy pomożesz towarzyskim duchom grać w tę grę?

Wejście:

Pierwsza linia wejścia zawiera jedną liczbę całkowitą $n$ - liczbę duchów. ( $1 \leq n \leq 5\cdot 10^{5}$ ). W kolejnych $n$ liniach znajdują się pary liczb całkowitych $x_{i}$ , $y_{i}$ - współrzędnych punktów reprezentujących kolejne duchy. ( $0 \leq x_{i}, y_{i} \leq 10^{8}$ ). Punkty będą parami różne.

Wyjście:

Wyjście powinno składać się z $n$ linii - po jednej dla każdego ducha w kolejności w jakiej współrzędne duchów pojawiały się na wejściu. Dla każdego ducha należy wypisać jedną liczbę $c_{i}$ zaokrągloną do dwóch miejsc po przecinku - najmniejszą odległość jaką musi przebyć ten duch (liczoną standardowo na płaszczyźnie) aby utworzyć kwadrat z pewnym innym duchem.