Cod sursa(job #2491916)

Utilizator melaa70Mela 70 melaa70 Data 13 noiembrie 2019 15:21:43
Problema Cele mai apropiate puncte din plan Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 1.29 kb
fin=open("cmap.in",'r')
n=fin.readline()
n=int(n)
coordinates=[]

for i in range(n):
    x,y=fin.readline().split()
    x, y = float(x), float(y)
    coordinates.append([x,y])

fin.close()

fout=open("cmap.out",'w')

from math import sqrt

def distance(A,B):
    return sqrt((A[0]-B[0])**2+(A[1]-B[1])**2)

def bruteForce(P,n):
    minim=1000

    for i in range(n):
        for j in range(i+1,n):
            if distance(P[i],P[j])<minim:
                minim=distance(P[i],P[j])
    return minim

def sortSecond(val):
    return val[1]

def strip(D,d):
    D.sort(key=sortSecond)
    minim=d

    for i in range(len(D)):
        for j in range(i+1,len(D)):
            if D[i][1]-D[j][1]<minim:
                if distance(D[i],D[j])<minim:
                    minim=distance(D[i],D[j])
    return minim

def closest(P,n):
    if n<=3:
        return bruteForce(P,n)

    mid=n//2
    midPoint=P[mid]
    d1=closest(P,mid)
    d2=closest([P[x] for x in range(mid,len(P))], n-mid)
    d=min(d1,d2)

    D=[]
    for point in P:
        if abs(point[0]-midPoint[0])<d:
            D.append(point)

    return min(d,strip(D,d))

def sortFirst(val):
    return val[0]

coordinates.sort(key=sortFirst)

fout.write(str(closest(coordinates,n)))
fout.close()