4155 - Harta3

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 , unde  și  sunt coordonatele acestora.

Exemplu:

harta3.in

4
1 2
2 -1
6 5
4 2

harta3.out

9.7678

Rezolvare

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()