1622 - Elicoptere

Cerința

Arhipelagul Zopopan este format din n insule de formă triunghiulară numerotate de la 1 la n. Fiecare insulă este localizată prin coordonatele carteziene ale vârfurilor.

Administrația dorește să cumpere elicoptere pentru a realiza transportul între insule. Un elicopter va putea să asigure o rută între două insule pe distanța minimă obținută pe orizontală sau verticală (paralel cu axele de coordonate). În plus, datorită capacității rezervorului o astfel de rută nu poate să depășească o valoare k – număr natural. Elicopterele parcurg rutele în ambele sensuri. Investiția trebuie să îndeplinească următoarele condiții:

Numărul de elicoptere cumpărate să fie minim. Numărul de perechi de insule între care se poate realiza transportul, folosind unul sau mai multe elicoptere să fie maxim. Suma lungimii tuturor rutelor să fie minimă. Să se scrie un program care pentru n, k şi coordonatele vârfurilor insulelor cunoscute, determină:

• numărul minim de elicoptere ce vor fi cumpărate de administraţie;
• numărul perechilor neordonate de insule între care se poate realiza transportul prin elicoptere direct sau indirect;
• suma distantelor parcurse de toate elicopterele cumpărate (distanța parcursă de un elicopter se consideră distanța dintre insulele între care acesta asigură transportul).

Date de intrare

Fișierul de intrare elicoptere.in conține pe prima linie o valoare v ce poate fi 1, 2, sau 3, în funcţie de cerinţa ce va fi rezolvată, pe linia a doua numerele naturale n şi k separate printr-un spaţiu, cu semnificaţia de mai sus, iar pe următoarele n linii se află câte şase numere naturale x1, y1, x2, y2, x3 și y3 separate prin spațiu reprezentând coordonatele celor trei vârfuri ale insulelor în formatul (abscisă, ordonată).

Date de ieșire

Dacă valoarea lui v este 1 atunci fişierul de ieşire elicoptere.out va conţine pe prima linie numai numărul minim de elicoptere, ce vor fi cumpărate de administraţie.

Dacă valoarea lui v este 2 atunci fişierul de ieşire elicoptere.out va conţine pe prima linie numai numărul maxim de perechi de insule între care se poate realiza transportul prin elicoptere.

Dacă valoarea lui v este 3 atunci fişierul de ieşire elicoptere.out va conţine pe prima linie suma minimă a lungimii rutelor parcurse de elicoptere.

Restricții și precizări

• 1 ≤ n ≤ 100;
• 1 ≤ k ≤ 1000;
• coordonatele vârfurilor insulelor sunt numere naturale 0 ≤ xi , yi ≤ 106;
• orice două insule nu au puncte comune;
• la cerința 2, dacă se poate ajunge din insula A în insula B atunci evident că se poate ajunge și din B în A, *deci perechea formată din A și B se numără o singură dată;
• distanța dintre două insule poate fi şi număr real. La cerința 3 rezultatul se cere cu o aproximație de 0.001, adică rezultatul notat cu R se consideră corect, dacă faţă de rezultatul comisiei C îndeplineşte condiţia |R-C|<0.001.
• pentru a calcula şi afișa un număr real x cu o precizie cât mai mare vă recomandăm folosirea tipului double

Exemplu 1

Intrare

1
6 11
100 20 100 30 105 30
20 20 30 30 20 30
200 20 200 30 205 30
100 40 100 50 105 40
10 40 5 40 10 50
10 20 5 30 10 30

Iesire

3

Rezolvare

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