Занятие 15

Тимур и его друзья, приехав летом на свои старые дачи, решили устроить на время своего отдыха игру. Они организовали команду, чтобы тайно помогать жителям дачного городка в их повседневных делах.

Дачный поселок довольно большой, и дома, в которых живут друзья Тимура, расположены далеко друг от друга. Как быстро передавать друг другу сообщения? Как собирать ребят на совет?

Тимур решил проложить веревочный телеграф, который связал бы все домики, в которых живут ребята из его команды. Всего домиков `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