Связанное множество
(Время: 1 сек. Память: 16 Мб Сложность: 58%)
Даны несколько точек на плоскости, некоторые из которых соединены отрезками. Множество точек называется связанным, если из любой его точки можно перейти в любую точку, перемещаясь только по отрезкам (переходить с отрезка на отрезок возможно только в точках исходного множества). Можно за определенную плату добавлять новые отрезки (стоимость добавления равна длине добавляемого отрезка). Требуется за минимальную стоимость сделать данное множество связанным.
Входные данные
В первой строке входного файла INPUT.TXT содержится одно целое число N (1 ≤ N ≤ 50) – количество точек. Далее в N строках записано по 2 натуральных числа – координаты точек (координаты не превышают 100). Все точки различны. Далее дано число M – количество уже существующих отрезков. В следующих M строках записаны по 2 числа – номера начала и конца соответствующего отрезка.
Выходные данные
В выходной файл OUTPUT.TXT выведите единственное число – минимально возможную стоимость дополнения с точностью, не худшей, чем 5 знаков после запятой.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3
1 1
1 2
10 1
1
2 1 | 9.0 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
