e-olymp
Соревнования

Spanning Tree + DSU

Подземные кабеля

Город хочет избавиться от своих неприглядных электроопор, переместив силовые кабели под землю. Имеется список опор, которые должны быть соединены между собой с некоторыми ограничениями. Туннельное оборудование может перемещаться только по прямой линии между точками. В любой точке города имеется место только для одного подземного кабеля, за исключением самих опор, так что никакие два кабеля не могут пересекаться.

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

Входные данные

Состоит из нескольких тестов. Каждый тест начинается количеством точек n (2n1000) в городе. Каждая из следующих n строк содержит два целых числа x и y (-1000x, y1000), где (x, y) - местоположения n точек. Все точки различны. Последняя строка содержит один 0.

Выходные данные

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

Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные #1
4
0 0
0 10
10 0
10 10
2
0 0
10 10
0
Выходные данные #1
30.00
14.14
Источник 2010 ACM North America, Mid-Atlantic, Problem H