kablovi

U nekom naselju koje ima N zgrada potrebno je uvesti telefonsku mrežu. Za svaku od N zgrada poznate su x i y koordinata lokacije na mapi na kojoj se zgrada nalazi. Potrebno je projektovati takvu funkcionalnu mrežu telefonskih kablova da se za povezivanje zgrada potroši što je god moguce manje kabla. Mreža je funkcionalna ukoliko postoji kablovska veza izmedu svake dvije zgrade, koja ne mora nužno biti direktna, nego može prolaziti i kroz druge zgrade. Kablovi se prostiru pravolinijski (tj. najkracim putem) od zgrade do zgrade, a jedine tacke u kojima se kablovi mogu medusobno vezati u mrežu (tj. jedine tacke u kojima se mreža kablova razgranava) jesu upravo zgrade. Na primjer, na slijedecoj slici je prikazan primjer minimalne mreže kablova za slucaj 6 zgrada rasporedenih kao na slici:<br><br>
<img src="./tasks/kablovi/kablovi.gif"><br><br>


Dužina pojedinih kablova racuna se kao Euklidsko rastojanje izmedu njegovih krajeva, dok je dužina mreže ukupna dužina svih kablova koji cine mrežu. Napomenimo da minimalna mreža ne mora biti jedinstvena (ali je ukupna dužina svih kablova u minimalnoj funkcionalnoj mreži naravno jedinstvena).<br><br>

Ulaz:<br>
U prvom redu standardnog ulaza se nalazi broj zgrada N, koji je u opsegu od 1 do 100 ukljucivo. U narednih N redova nalazi se N parova x i y koordinata svake od zgrada. Sve koordinate su cijeli brojevi u opsegu od 0 do 100 ukljucivo, a medusobno su razdvojene po jednim razmakom.<br><br>
Izlaz:
U prvi red standardnog ulaza potrebno je zapisati dužinu minimalne funkcionalne mreže kablova zaokruženu na dvije decimale (s obzirom da tražena dužina tipicno nije cijeli broj).<br><br>

Primjeri:<br><br>

Ulaz<br>
6<br>
1 1<br>
3 1<br>
1 3<br>
3 3<br>
2 2<br>
4 1<br>
<br>
Izlaz<br>
6.66<br>
<br>
Ulaz<br>
4<br>
1 0<br>
2 0<br>
3 0<br>
4 0<br>
<br>
Izlaz<br>
3.00<br>
<br>
Ulaz<br>
8<br>
3 5<br>
2 0<br>
7 8<br>
4 6<br>
4 9<br>
5 2<br>
0 0<br>
8 6<br>
<br>
Izlaz<br>
19.02