Kablovi

Opis zadatka:

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 moguće manje kabla. Mreža je funkcionalna ukoliko postoji kablovska veza između svake dvije zgrade, koja ne mora nužno biti direktna, nego može prolaziti i kroz druge zgrade. Kablovi se prostiru pravolinijski (tj. najkraćim putem) od zgrade do zgrade, a jedine tačke u kojima se kablovi mogu međusobno vezati u mrežu (tj. jedine tačke u kojima se mreža kablova razgranava) jesu upravo zgrade. Na primjer, na slijedećoj slici je prikazan primjer minimalne mreže kablova za slučaj 6 zgrada raspoređenih kao na slici:

Dužina pojedinih kablova računa se kao Euklidsko rastojanje između njegovih krajeva, dok je dužina mreže ukupna dužina svih kablova koji čine 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).

Izvršna datoteka treba da se nalazi u direktoriju C:\BHOI2003 pod imenom KABLOVI.EXE.

Ulazna datoteka:

Ulazni podaci nalaze se u tekstualnoj datoteci KABLOVI.IN. U prvom redu se nalazi broj zgrada N, koji je u opsegu od 1 do 100 uključivo. 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 uključivo, a međusobno su razdvojene po jednim razmakom.

Izlazna datoteka:

U prvi i jedini red izlazne tekstualne datoteke KABLOVI.OUT potrebno je zapisati dužinu minimalne funkcionalne mreže kablova zaokruženu na dvije decimale (s obzirom da tražena dužina tipično nije cijeli broj).

Vremensko ograničenje:

Za svaki testni primjer program treba da ponudi rješenje za najviše 10 sekundi.

Primjeri:

KABLOVI.IN
6
1 1
3 1
1 3
3 3
2 2
4 1
KABLOVI.OUT
6.66
KABLOVI.IN
4
1 0
2 0
3 0
4 0
KABLOVI.OUT
3.00
KABLOVI.IN
8
3 5
2 0
7 8
4 6
4 9
5 2
0 0
8 6
KABLOVI.OUT
19.02

[Testni podaci] [Rješenje (Pascal)] [Rješenje (C++)]