| Fişierul intrare/ieşire: | cablaj.in, cablaj.out | Sursă | OLI 2009, Brasov, clasele 11-12 |
| Autor | Doru Modrisan | Adăugată de |  Andrei Misarca •Mishu91 |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 4736 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Cablaj
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.
Date de intrare
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.
Date de ieşire
Fişierul de ieşire cablaj.out va conţine un numar real reprezentând lungimea minimă totală a cablului necesar.
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.
Exemplu
| cablaj.in | cablaj.out |
|---|---|
| 4 7 4 7 7 11 10 1 15 | 18.00 |
