Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2332. Гиперкик
Предрасчеты, кэширование вычисленийОлимпиадные задачи на русском языке
| 02/04/2017 | Открытые командные соревнования по спортивному программированию "PRIME TIME" ( 9) |
Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
В недалеком будущем искусственный интеллект "Ватсон" изобрел новый вид
транспорта – гиперкик. Перемещение по гиперкику происходит почти мгновенно, независимо от длины и
формы линии. Также очень быстро происходит пересадка с одной линии на другую. Но строительство станций
и линий гиперкика стоит дорого, поэтому станции будут построены только в городах. Стоимость строительства
линии прямо пропорциональна её длине. Ведение строительства затрудняет горный хребет, через который невозможно
построить линию, поэтому линии гиперкика должны идти в обход хребта. Для упрощения будем считать хребет
отрезком прямой линии. Необходимо связать все города страны линиями гиперкика таким образом, чтобы можно
было попасть из любого города в любой другой и стоимость строительства была минимальна.
Формат ввода
Первая строка ввода содержит пять целых чисел – количество городов `N` (`2\ ≤\ N\ ≤\ 3000`)
и координаты концов отрезка-хребта `X_1,\ Y_1,\ X_2,\ Y_2` (`0\ ≤\ X_1,\ Y_1,\ X_2,\ Y_2\ ≤\ 10000`).
Далее следует `N` строк, содержащих по два целых числа в диапазоне от 0 до 10000 – координаты городов.
Гарантируется, что координаты городов не совпадают и не попадают на хребет.
Формат вывода
Вывести одно число – минимальную суммарную длину линий с точностью `10^{-5}`.
Пример ввода
3 1 5 4 1 2 2 3 5 5 3
Пример вывода
7.30056
