cablaj

Cablaj

== include(page="template/taskheader" task_id="cablaj") ==

Poveste şi cerinţă...

Compania judeţeană de distribuire a curentului electric a decis că reţeaua de cabluri a judeţului trebuie complet înlocuită din cauza uzurii cablurilor. Reţeaua trebuie astfel concepută încât, între oricare două localităţi ale judeţului să existe legătură prin cablu (care poate fi sau directă, sau indirectă, adică trecând prin oricâte alte localităţi). Costul cablării dintre două localităţi este direct proporţional cu distanţa dintre cele două localităţi. Fiecare dintre localităţi este reperată în cadrul hărţii judeţului prin coordonatele sale carteziene, într-un sistem de coordonate având originea undeva în sud-vestul judeţului, astfel încât toate coordonatele oricărei localităţi să fie pozitive. Directorul companiei, fiind foarte ocupat, vă roagă pe voi sa determinaţi lungimea minimă a cablului necesar cablării tuturor celor $N$ localităţi.
 

h2. Date de intrare

Fişierul de intrare $cablaj.in$ ...

Fişierul de intrare $cablaj.in$ va conţine pe prima linie $N$, numărul de localităţi, iar pe urmatoarele $N$ linii coordonatele localităţilor.

h2. Date de ieşire

În fişierul de ieşire $cablaj.out$ ...

Fişierul de ieşire $cablaj.out$ va conţine un numar real reprezentând lungimea minimă totală a cablului necesar.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 3.000$
* $0 ≤ coordonatele oricărei localităţi ≤ 30.000$
* Nu vor exista mai multe localităţi aflate la aceleaşi coordonate.
* Se va accepta o eroare de maxim $0.001$.

h2. Exemplu
table(example). |_. cablaj.in |_. cablaj.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 4
  7 4
  7 7
  11 10
  1 15
| 18.00

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="cablaj") ==

4699