images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
05/12/2025 17:17:40

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

704. Острова

Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

В океане есть архипелаг из `N` прямоугольных островков. Стороны прямоугольников расположены параллельно осям координат. Чтобы переходить с острова на остров, не замочив ног, Робинзону, потерпевшему кораблекрушение на архипелаге, приходится носить с собой длинную доску. Напишите программу, вычисляющую минимальную длину доски, с помощью которой Робинзон сможет попасть с любого острова на любой другой. Переходить на нужный остров можно, используя в качестве промежуточных пунктов путешествия остальные острова. Длина доски, необходимая для перехода с одного острова на другой, равна расстоянию между ближайшими точками этих островов.
В первой строке входного файла содержится одно целое число `N` (`2\ ≤\ N\ ≤\ 100`) – количество островков. Далее следует `N` строк, каждая строка содержит четыре целых числа `x_1,\ y_1,\ x_2,\ y_2`, разделенных пробелами – координаты противоположных углов прямоугольного острова (`0\ <\ x_1\ <\ x_2\ <\ 1000`, `0\ <\ y_1\ <\ y_2\ <\ 1000`). Острова не накладываются друг на друга и не соприкасаются.
В первой строке выходного файла вывести одно число с точностью `10^{-3}` – минимальную длину доски для путешествия.

Пример ввода

3
1 3 3 4
3 1 4 2
5 3 6 4

Пример вывода

1.414
loading