Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
704. Острова
Вычислительная геометрияКратчайшие пути между всеми парами вершин
Олимпиадные задачи на русском языке
| 30/04/2006 | Региональная олимпиада Информатика-2006 (3) |
| 21/11/2007 | Занятие 11 (B) |
| 13/03/2010 | Занятие 10 (E) |
| 09/12/2010 | Сборы 31 (3F) |
| 23/12/2010 | Сборы 31: Тренировка 3 (F) |
| 09/03/2011 | Занятие 16 (C) |
| 01/12/2012 | Занятие 12 (A) |
| 18/11/2014 | Занятие 11 (D) |
| 09/07/2018 | Лето 2018 - 7 (C) |
| 13/07/2020 | Лето 2020 - 6 (C) |
| 17/02/2023 | «Базовая олимпиадная подготовка» (second level) - алгоритм Дейкстры (проводит novink) (C) |
| 27/02/2023 | Входной контроль (маги) (проводит sartasova) (D) |
Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение 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
