ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

УрКОП 2020

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

H. Полёт на ядре

Ограничение времени: 2.0 секунды
Ограничение памяти: 256 МБ
Барон Мюнхгаузен участвует в очередной баталии, которая происходит на плоскости с прямоугольной декартовой системой координат. Командир приказал ему как можно быстрее попасть в центр координат. Дело за малым — нужно сесть на ядро и спрыгнуть с него как можно ближе к цели.
На поле есть n пушечных батарей, и Мюнхгаузен находится в одной из них. Батареи можно считать точками, i-я батарея имеет координаты (xi, yi). Находясь в одной из батарей, барон может выстрелить в сторону любой другой батареи и сесть на ядро; стрелять мимо батареи нельзя — это подорвёт авторитет барона. Ядро не останавливается, достигнув батареи, а продолжает лететь бесконечно далеко. Пролетая над любой из батарей, Мюнхгаузен может спрыгнуть с ядра; после этого он снова сможет выстрелить в сторону другой батареи. Таким образом барон может свободно перемещаться между батареями.
Когда барон решит, что он близок к центру координат, он спрыгнет с ядра и дальше пойдёт пешком. Определите наименьшее расстояние, на которое барон Мюнхгаузен может приблизиться к центру координат, перемещаясь только на ядрах.

Исходные данные

В первой строке задано целое число n (2 ≤ n ≤ 105) — количество батарей.
В следующих n строках заданы целые числа xi и yi, разделённые пробелом (−105xi, yi ≤ 105) — координаты очередной батареи. Гарантируется, что не существует двух батарей с совпадающими координатами.

Результат

Выведите одно действительное число — наименьшее расстояние, на которое барон Мюнхгаузен может приблизиться к центру координат, перемещаясь только на ядрах. Ваш ответ считается правильным, если абсолютная или относительная его погрешность не превышает 10−6.

Примеры

исходные данныерезультат
4
1 0
0 1
-1 0
0 -1
0.0000000000
5
0 3
1 2
1 3
1 4
2 3
0.7071067812

Замечания

Иллюстрация ко второму примеру:
Problem illustration
Автор задачи: Валентин Зуев
Источник задачи: Уральская командная олимпиада по программированию 2020
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2154. Полёт на ядре