Cod sursa(job #2487792)

Utilizator andra_racovitaRacovita Andra-Georgiana andra_racovita Data 5 noiembrie 2019 18:47:45
Problema Cele mai apropiate puncte din plan Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 1.86 kb
#Citire date
#date=open("date.in","r")
date=open("cmap.in","r")
out=open("cmap.out","w")

n=int(date.readline())
p=[]#Punctele
for i in range(n):
    line=date.readline().split()
    p.append((int(line[0]),int(line[1])))
#p.sort()

def merge(st,m,dr,p):
    i=st
    j=m+1
    r=[]
    while i<=m and j<=dr:
        if(p[i][1]<p[j][1]):
            r.append(p[i])
            i+=1
        else:
            r.append(p[j])
            j+=1
    while i<=m:
        r.append(p[i])
        i+=1
    while j<=dr:
        r.append(p[j])
        j+=1
    for i in range(st,dr+1):
        p[i]=r[i-st]


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

def dist_min(st,dr,p):
    #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
    dst=dist_min(st,mp,p)
    ddr=dist_min(mp+1,dr,p)
    d=min(dst,ddr)
    #Se sorteaza partea st si dr dupa ordonata
    merge(st,mp,dr,p)

    mx=p[mp][0]#Coordonata x a punctului din mijloc
    #Punem elementele in banda, care se afla la distanta d fata de mx
    B=[]
    for i in range(st,dr+1):
        if abs(p[i][0]-mx)<=d:
            B.append(p[i])
 
    #Pt a aflat dist min din banda folosim sortarea dupa y
    #Acum verificam daca exista o distanta mai mica in banda
    dBmin=999999999999
    for i in range(len(B)):
        for j in range(i+1,i+8):
            if j<len(B):
                dB=calcul_dist(B[i],B[j])
                d=min(d,dB)
    return d

d=dist_min(0,n-1,p)
out.write(d)