Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
801. Веревочный телеграф
Минимальное остовное деревоОлимпиадные задачи на русском языке
| 27/02/2008 | Занятие 15 (A) |
| 03/03/2012 | Занятие 10 (E) |
| 10/01/2023 | Остовные деревья (проводит BOGAT) (A) |
| 16/09/2024 | Остовные деревья, СНМ (проводит BOGAT) (A) |
Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Тимур и его друзья, приехав летом на свои старые дачи, решили устроить на время своего отдыха игру.
Они организовали команду, чтобы тайно помогать жителям дачного городка в их повседневных делах.
Дачный поселок довольно большой, и дома, в которых живут друзья Тимура, расположены далеко друг от друга.
Как быстро передавать друг другу сообщения? Как собирать ребят на совет?
Тимур решил проложить веревочный телеграф, который связал бы все домики, в которых живут ребята из его команды.
Всего домиков `N`. По карте ребята вычислили координаты каждого домика `(X_i,\ Y_i)` в целых числах и выписали их на бумаге.
За единицу измерения координат они взяли один метр. Однако возник вопрос: какие домики нужно соединять веревочным телеграфом,
чтобы связь была между всеми домиками (возможно, через другие домики), а общая длина всех веревок была как можно меньше?
Требуется написать программу, которая по координатам домиков определяла бы, какова минимальная общая длина всех веревок,
соединяющих все домики между собой (возможно, через другие домики).
Первая строка ввода содержит одно целое число `N` `(0<N≤1000)`. Далее следует `N` строк содержащих два целых числа `X_i`,
`Y_i` (`-32000\ ≤\ X_i,\ Y_i≤\ 32000`).
Вывести одно число – минимальную длину веревок с точностью `10^{-2}`.
Пример вывода
5 100 200 200 200 300 400 400 200 400 100
Пример вывода
623.61
