Fişierul intrare/ieşire:cablaj.in, cablaj.outSursăOLI 2009, Brasov, clasele 11-12
AutorDoru ModrisanAdăugată deMishu91Andrei Misarca Mishu91
Timp execuţie pe test0.15 secLimită de memorie4736 kbytes
Scorul tăuN/ADificultateN/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.incablaj.out
4
7 4
7 7
11 10
1 15
18.00
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content