Runda 23 [Hard] - Duchy

13.06.2011 - Damian Rusak
TrudnośćTrudność

 

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.

Przykład:

Wejście:

5
8 5
5 2
9 4
0 8
0 2

Wyjście:

0.00
0.00
0.00
0.71
3.54

 

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com