Cod sursa(job #2491765)

Utilizator Natasa_CNatasa Cirstea Natasa_C Data 13 noiembrie 2019 08:59:40
Problema Cele mai apropiate puncte din plan Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 2.01 kb
from operator import itemgetter
import math

def distance_2(point1, point2):
    global dist
    dist = math.sqrt((point1[0] - point2[0]) * (point1[0] - point2[0]) + (point1[1] - point2[1]) * (point1[1] - point2[1]))

def distance_3(point1, point2,point3):
    global dist

    dist_1_2 = math.sqrt((point1[0] - point2[0]) * (point1[0] - point2[0]) + (point1[1] - point2[1]) * (point1[1] - point2[1]))
    dist_1_3 = math.sqrt((point1[0] - point3[0]) * (point1[0] - point3[0]) + (point1[1] - point3[1]) * (point1[1] - point3[1]))
    dist_2_3 = math.sqrt((point2[0] - point3[0]) * (point2[0] - point3[0]) + (point2[1] - point3[1]) * (point2[1] - point3[1]))

    dist = min(dist_1_2,dist_1_3,dist_2_3)

def get_distance(m):
    global dist_min
    global dist
    band = []

    for point in X:
        if point[0] > X[m][0] - dist_min and point[0] < X[m][0] + dist_min:
            band.append(point)
    
    band = sorted(band, key = itemgetter(1))
    
    for i in range(len(band) - 7):
        for j in range(1,8):
            dist = 0 
            distance_2(band[i],band[i+j])
            if dist < dist_min:
                dist_min = dist

def divide(X):
    global dist_min
    global dist

    if len(X) > 3:
        m = len(X) // 2
    
        left_x = X[:m+1]
        right_x = X[m:]
            
        divide(left_x)
        divide(right_x)

        get_distance(m)

    elif (len(X) == 3):
        dist = 0
        distance_3(X[0],X[1],X[2])
        if dist < dist_min:
            dist_min = dist

    elif (len(X) == 2):
        dist = 0
        distance_2(X[0],X[1])
        if dist < dist_min:
            dist_min = 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 = sorted(X, key = itemgetter(0))

# # sort points on y
# Y = sorted(X, key = itemgetter(1))

dist = 0
dist_min = math.inf

divide(X)

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