eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

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

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

Город хочет избавиться от своих неприглядных электроопор, переместив силовые кабели под землю. Имеется список опор, которые должны быть соединены между собой с некоторыми ограничениями. Туннельное оборудование может перемещаться только по прямой линии между точками. В любой точке города имеется место только для одного подземного кабеля, за исключением самих опор, так что никакие два кабеля не могут пересекаться. По заданному списку точек определить наименьшее количество кабеля, необходимого для соединения каждой пары точек либо непосредственно, либо косвенно через другие пункты. \InputFile Состоит из нескольких тестов. Каждый тест начинается количеством точек $n~(2 \le n \le 1000)$ в городе. Каждая из следующих $n$ строк содержит два целых числа $x$ и $y~(-1000 \le x, y \le 1000)$, где $(x, y)$ --- местоположения $n$ точек. Все точки различны. Последняя строка содержит один $0$. \OutputFile Для каждого теста вывести одно действительное число, равное длине кабеля, достаточного для соединения всех точек города. Вывести это число с двумя десятичными знаками. Ответ на каждый тест выводить в отдельной строке. Не выводите пустые строки между ответами на тесты. \includegraphics{https://static.e-olymp.com/content/bf/bfcdadc3190de68d9fc6a1627e8abfb224f3a4ae.gif}
Ліміт часу 1 секунда
Ліміт використання пам'яті 128 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