Cod sursa(job #2489124)

Utilizator codry99Apetrei Codrin Andrei codry99 Data 7 noiembrie 2019 22:19:42
Problema Cele mai apropiate puncte din plan Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 1.01 kb
f = open("cmap.in", "r")
n = int(f.readline())
Puncte = []
for i in range( n ):
    pereche = f.readline().split()
    pereche = (int(pereche[0]), int(pereche[1]))
    Puncte.append(pereche)
Puncte.sort()
import math
def distanta(Punct1, Punct2):
    return (math.sqrt((Punct1[0]-Punct2[0])*(Punct1[0]-Punct2[0])+(Punct1[1]-Punct2[1])*(Punct1[1]-Punct2[1])))
def DEI( st, dr ):
    if(dr - st <= 3):
        dist = distanta(Puncte[0], Puncte[1])
        if (dr - st == 3):
            dist = min(dist, distanta(Puncte[0], Puncte[2]))
            dist = min(dist, distanta(Puncte[1], Puncte[2]))
        return dist
    med = st + (dr - st)/2
    dist = min( DEI(st, med), DEI(med, dr) )
    aux = []
    lungime = 0
    for i in range (int(st), int(dr)):
        aux.append((Puncte[i][1], Puncte[i][0]))
        lungime += 1
    aux.sort()
    for i in range (lungime):
        for j in range (i+1, lungime):
            dist = min(dist, distanta(aux[i], aux[j]))
    return dist
print(round(DEI(0, n),6))