Danciu: Pagină nouă: = 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ă...

2024-06-04T03:30:31Z

Pagină nouă: = Cerința = Harta unei regiuni este reprezentată într-un sistem de coordonate cartezian și sunt cunoscute coordonatele a <code>n</code> orașe, numerotate de la <code>1</code> la <code>n</code>. 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ă...

New page

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

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 <code>harta3.in</code> conține pe prima linie numărul de orașe <code>n</code>, iar pe fiecare dintre următoarele <code>n</code> linii câte două numere întregi <code>x y</code>, reprezentând coordonatele acestora.

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

= Restricții și precizări =

* <code>1 ≤ n ≤ 100</code>;
* coordonatele orașelor sunt din intervalul <code>[-200, 200]</code>;
* lungimea drumului dintre două orașe se determină cu formula , unde și sunt coordonatele acestora.

= Exemplu: =
<code>harta3.in</code>
4
1 2
2 -1
6 5
4 2
<code>harta3.out</code>
9.7678

== Explicație ==

== Rezolvare ==
<syntaxhighlight lang="python3">
import math

class Muchie:
def __init__(self, i, j, cost):
self.i = i
self.j = j
self.cost = cost

def find(P, i):
if P[i] == i:
return i
else:
P[i] = find(P, P[i])
return P[i]

def union(P, rank, x, y):
root_x = find(P, x)
root_y = find(P, y)
if root_x != root_y:
if rank[root_x] > rank[root_y]:
P[root_y] = root_x
elif rank[root_x] < rank[root_y]:
P[root_x] = root_y
else:
P[root_y] = root_x
rank[root_x] += 1

def main():
with open("harta3.in", "r") as fin:
n = int(fin.readline().strip())
x = [0] * (n + 1)
y = [0] * (n + 1)
for i in range(1, n + 1):
x[i], y[i] = map(int, fin.readline().strip().split())

M = []
for i in range(1, n):
for j in range(i + 1, n + 1):
cost = math.sqrt((x[i] - x[j]) ** 2 + (y[i] - y[j]) ** 2)
M.append(Muchie(i, j, cost))

M.sort(key=lambda muchie: muchie.cost)

P = [i for i in range(n + 1)]
rank = [0] * (n + 1)
S = 0.0

for muchie in M:
if find(P, muchie.i) != find(P, muchie.j):
union(P, rank, muchie.i, muchie.j)
S += muchie.cost

with open("harta3.out", "w") as fout:
fout.write(f"{S:.4f}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

4155 - Harta3 - Revision history