Назад
 Начало |
 Соревнования |
| 2006 |
Подразделы
Другие разделы
Дата и время
13/03/2025 13:27:58
Региональная олимпиада по информатике (очный тур)
3. Острова
Вычислительная геометрияКратчайшие пути между всеми парами вершин
Олимпиадные задачи на русском языке
| 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) |
| 15/02/2025 | Входной контроль (маги) (проводит sartasova) (D) |
| 15/02/2025 | Входной контроль (магистры) (проводит sartasova) (D) |
Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
В океане есть архипелаг из N прямоугольных островков. Стороны прямоугольников расположены параллельно осям координат. Чтобы переходить с острова на остров, не замочив ног, Робинзону, потерпевшему кораблекрушение на архипелаге, приходится носить с собой длинную доску. Напишите программу, вычисляющую минимальную длину доски, с помощью которой Робинзон сможет попасть с любого острова на любой другой. Переходить на нужный остров можно, используя в качестве промежуточных пунктов путешествия остальные острова. Длина доски, необходимая для перехода с одного острова на другой, равна расстоянию между ближайшими точками этих островов.
В первой строке входного файла содержится одно целое число N (2 ) – количество островков. Далее следует 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
