06/04/2025 23:18:30

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

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

2332. Гиперкик

Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение 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}$ .

Пример ввода

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

7.30056