Cod sursa(job #2491892)

Utilizator melaa70Mela 70 melaa70 Data 13 noiembrie 2019 14:14:50
Problema Cele mai apropiate puncte din plan Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 1.26 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)

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

def closest(P,n):
    if n<=3:
        return bruteForce(P,n)
    else:
        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 strip(D,d)

def sortFirst(val):
    return val[0]

coordinates.sort(key=sortFirst)

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