e-olymp
Yarışlar

Spanning Tree + DSU

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

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

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

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

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

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

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
4
0 0
0 10
10 0
10 10
2
0 0
10 10
0
Çıxış verilənləri #1
30.00
14.14
Mənbə 2010 ACM North America, Mid-Atlantic, Problem H