Городские олимпиады/1-6 курсы/Межвузовская олимпиада 2014 - командный тур


4. Точки на стене

Автор задачи: Александр Пак
Ограничение по времени: 2.5 с.
Ограничение по памяти: 64 МБ

Источник: командный тур межвузовской олимпиады 2014 года

Проезжая на велосипеде по луже Александр заметил, что брызги от его колес легли на ближайшую белую стену в виде множества некрасивых серых точек.

Местный охранник поймал Александра и заставил его отмывать стену, а в качестве дополнительного наказания он хочет, чтобы Александр для каждой точки нашел ближайшую к ней.

Входные данные

В первой строке дано целое число N (2 ≤ N ≤ 50000) — количество точек.

В последующих N строках даны координаты точек — по два целых числа на строку через пробел. Координаты целые, лежат в интервале [0..216). Гарантируется, что все точки различны.

Выходные данные

Выходной поток должен содержать N чисел по одному на строку — расстояния до ближайших точек. Расстояния выводить округленными до шести знаков после запятой. Расстояния выводить для точек в том же порядке, в каком они перечислены во входных данных.

Пример

Стандартный вводСтандартный вывод
2
0 9
3 3
6.708204
6.708204