Editing 1622 - Elicoptere (section)

== Rezolvare ==
<syntaxhighlight lang="python" line>
import math

def citire_date_intrare():
    with open("elicoptere.in", "r") as f:
        lines = f.readlines()
    
    p = int(lines[0].strip())
    n, k = map(int, lines[1].strip().split())
    insule = []
    for line in lines[2:]:
        insula = tuple(map(int, line.strip().split()))
        insule.append(insula)
    
    return p, n, k, insule

def distanta(x1, y1, x2, y2):
    return math.sqrt((x1 - x2)**2 + (y1 - y2)**2)

def rezolva_problema1(insule, n, k):
    vizitat = [False] * n
    numar_elicoptere = 0

    def dfs(nod):
        stack = [nod]
        while stack:
            nod_curent = stack.pop()
            for vecin in range(n):
                if not vizitat[vecin] and exista_legatura(insule[nod_curent], insule[vecin], k):
                    vizitat[vecin] = True
                    stack.append(vecin)

    for i in range(n):
        if not vizitat[i]:
            numar_elicoptere += 1
            vizitat[i] = True
            dfs(i)

    return numar_elicoptere

def rezolva_problema2(insule, n, k):
    numar_perechi = 0
    for i in range(n):
        for j in range(i + 1, n):
            if exista_legatura(insule[i], insule[j], k):
                numar_perechi += 1
    return numar_perechi

def rezolva_problema3(insule, n, k):
    graph = []
    for i in range(n):
        for j in range(i + 1, n):
            if exista_legatura(insule[i], insule[j], k):
                dist = calculeaza_distanta(insule[i], insule[j])
                graph.append((dist, i, j))
    graph.sort()

    parinte = list(range(n))

    def gaseste(parinte, i):
        if parinte[i] == i:
            return i
        parinte[i] = gaseste(parinte, parinte[i])
        return parinte[i]

    cost_total = 0
    muchii_folosite = 0

    for dist, u, v in graph:
        rad_u = gaseste(parinte, u)
        rad_v = gaseste(parinte, v)
        if rad_u != rad_v:
            cost_total += dist
            muchii_folosite += 1
            parinte[rad_u] = rad_v
            if muchii_folosite == n - 1:
                break

    return round(cost_total, 3)

def exista_legatura(insula1, insula2, k):
    for i in range(0, 6, 2):
        for j in range(0, 6, 2):
            dist = distanta(insula1[i], insula1[i+1], insula2[j], insula2[j+1])
            if dist <= k:
                return True
    return False

def calculeaza_distanta(insula1, insula2):
    min_dist = float('inf')
    for i in range(0, 6, 2):
        for j in range(0, 6, 2):
            dist = distanta(insula1[i], insula1[i+1], insula2[j], insula2[j+1])
            if dist < min_dist:
                min_dist = dist
    return min_dist

def main():
    p, n, k, insule = citire_date_intrare()
    
    # Verificare restrictii
    assert 1 <= n <= 100, "n trebuie să fie între 1 și 100"
    assert 1 <= k <= 1000, "k trebuie să fie între 1 și 1000"
    for x1, y1, x2, y2, x3, y3 in insule:
        assert 0 <= x1 <= 10**6 and 0 <= y1 <= 10**6, "Coordonatele trebuie să fie între 0 și 1,000,000"
        assert 0 <= x2 <= 10**6 and 0 <= y2 <= 10**6, "Coordonatele trebuie să fie între 0 și 1,000,000"
        assert 0 <= x3 <= 10**6 and 0 <= y3 <= 10**6, "Coordonatele trebuie să fie între 0 și 1,000,000"

    if p == 1:
        rezultat = rezolva_problema1(insule, n, k)
    elif p == 2:
        rezultat = rezolva_problema2(insule, n, k)
    elif p == 3:
        rezultat = rezolva_problema3(insule, n, k)
    else:
        print("Valoare p invalidă.")
        return

    with open("elicoptere.out", "w") as f:
        f.write(f"{rezultat}\n")

if __name__ == "__main__":
    main()


</syntaxhighlight>