Rezolvare PBinfo #4155

Cerința

Harta unei regiuni este reprezentată într-un sistem de coordonate cartezian și sunt cunoscute coordonatele a n orașe, numerotate de la 1 la n.

Se dorește construirea unor drumuri bidirecționale între anumite perechi de orașe, astfel încât:

• să se poate ajunge din orice oraș în oricare altul folosind unul sau mai multe dintre drumurile construite;
• suma lungimilor drumurilor construite să fie minimă.

Să se determine suma lungimilor drumurilor construite.

Date de intrare

Fișierul de intrare harta3.in conține pe prima linie numărul de orașe n, iar pe fiecare dintre următoarele n linii câte două numere întregi x y, reprezentând coordonatele acestora.

Date de ieșire

Fișierul de ieșire harta3.out va conține pe prima linie suma lungimilor drumurilor construite, cu cel puțin trei zecimale exacte.

Restricții și precizări

• 1 ≤ n ≤ 100;
• coordonatele orașelor sunt din intervalul [-200, 200];
• lungimea drumului dintre două orașe se determină cu formula \(\sqrt { \left(x_1-x_2\right)^2 + \left( y_1-y_2 \right)^2 } \), unde \( \left( x_1, y1 \right) \) și \( \left( x_2, y_2 \right) \) sunt coordonatele acestora.

Exemplu:

harta3.in

4
1 2
2 -1
6 5
4 2

harta3.out

9.7678

Explicație

Drumurile construite sunt desenate în imaginea de mai sus. Lungimile lor sunt:

• de la orașul 1 la orașul 4, lungime 3
• de la orașul 1 la orașul 2, lungime 3.16228
• de la orașul 3 la orașul 4, lungime 3.60555