Cod sursa(job #2492232)

Utilizator Natasa_CNatasa Cirstea Natasa_C Data 14 noiembrie 2019 10:47:29
Problema Cele mai apropiate puncte din plan Scor 10
Compilator py Status done
Runda Arhiva educationala Marime 1.55 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(X):
    
    if len(X) > 3:
        m = len(X) // 2
            
        dist_left = divide(X[:m+1])
        dist_right = divide(X[m:])

        dist_min = min(dist_left,dist_right)

        band = []


        i = m - 1
        while (i >= 0 and X[i][0] > X[m][0] - dist_min):
            band.append(X[i])
            i -= 1
        
        i = m + 1
        while (i < len(X) and X[i][0] < X[m][0] + dist_min):
            band.append(X[i])
            i += 1

        # for i in range(len(X)):
        #     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
    
    else:
        dist = math.inf
        for i in range(len(X)):
            for j in range(i+1, len(X)):
                dist = min(dist,distance_2(X[i],X[j]))
        return dist


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)))

# sort points on x
X.sort(key = itemgetter(0))

dist_min = math.sqrt(divide(X))

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