Cod sursa(job #2483605)

Utilizator andra_racovitaRacovita Andra-Georgiana andra_racovita Data 29 octombrie 2019 22:32:07
Problema Cele mai apropiate puncte din plan Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 1.42 kb
#Citire date
date=open("date.in","r")
n=int(date.readline())
p=[]#Punctele
for i in range(n):
    line=date.readline().split()
    p.append((int(line[0]),int(line[1])))

#X-sortat dupa x si Y sortat dupa y
x=sorted(p,key=lambda a:a[0])
y=sorted(p,key=lambda a:a[1])

from math import sqrt
def calcul_dist(a,b):
    d=abs((a[1]-a[0]))^2+abs((b[1]-b[0]))^2
    return sqrt(d)

def dist_min(st,dr):
    #Aflarea dist min din st si dr foloseste sortarea dupa 
    if dr-st+1<2:
        print("Un punct sau niciunul")
        return 0
    if dr-st+1==2:
        return calcul_dist(p[st],p[st+1])
    if dr-st+1==3:
        d1=calcul_dist(p[st],p[st+1])
        d2=calcul_dist(p[st],p[st+2])
        d3=calcul_dist(p[st+1],p[st+2])
        return min(d1,min(d2,d3))
    mp=(st+dr)//2
    mx=p[mp][0]#Coordonata x a punctului din mijloc
    dst=dist_min(st,mp)
    ddr=dist_min(mp+1,dr)
    #Pt a aflat dist min din banda folosim sortarea dupa y
    d=min(dst,ddr)

    #Punem elementele in banda, care se afla la distanta d fata de mx
    B=[]
    for i in range(st,dr+1):
        if abs(y[i][0]-mx)<=d:
            B.append(y[i])
    
    #Acum verificam daca exista o distanta mai mica in banda
    dB=999999999999
    for i in range(len(B)-1):
        for j in range(i+1,i+8):
            if j<len(B):
                dB=calcul_dist(B[i],B[j])

    dmin=min(d,dB)
    return dmin

d=dist_min(0,n-1)
print(d)