Cod sursa(job #2491810)

Utilizator Natasa_CNatasa Cirstea Natasa_C Data 13 noiembrie 2019 10:45:47
Problema Cele mai apropiate puncte din plan Scor 10
Compilator py Status done
Runda Arhiva educationala Marime 1.19 kb
from operator import itemgetter
import math

def distance_2(point1, point2):
    return (point1[0] - point2[0]) * (point1[0] - point2[0]) + (point1[1] - point2[1]) * (point1[1] - point2[1])

def divide(st, dr):

    if dr - st <= 3:
        dist = math.inf
        for i in range(st, dr+1):
            for j in range(i+1, dr+1):
                dist = min(dist,distance_2(X[i],X[j]))
        return dist

    m = st + (dr - st) // 2
    dist_s = divide(st,m)
    dist_d = divide(m+1,dr)
    dist_min = min(dist_s,dist_d)

    band = []
    for i in range(st,dr+1):
        if (abs(X[m][0] - X[i][0]) < dist_min):
            band.append(X[i])

    band.sort(key = itemgetter(1))

    for i in range(len(band) - 7):
        for j in range(1,8):
            dist = distance_2(band[i],band[i+j])
            if dist < dist_min:
                dist_min = dist

    return dist_min
    

fin = open("cmap.in","r")
text = fin.read()
lines = text.split("\n")
fin.close()

n = int(lines[0])
X = []

for i in range(n):
    x,y = lines[i+1].split()
    X.append((int(x),int(y)))

X.sort(key = itemgetter(0))

dist_min = math.sqrt(divide(0,len(X) - 1))

fout = open("cmap.out","w") 
fout.write("%.6f" % dist_min)
fout.close()