Cod sursa(job #2488186)

Utilizator Natasa_CNatasa Cirstea Natasa_C Data 6 noiembrie 2019 13:11:53
Problema Cele mai apropiate puncte din plan Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 2.22 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(left_x,left_y,right_x,right_y,m):
    global dist_min
    global dist
    band = []

    for point in Y:
        if point[0] > X[m][0] - dist_min and point[0] < X[m][0] + dist_min:
            band.append(point)
    
    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,Y):
    global dist_min
    global dist

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

        for point in Y:
            if point[0] < X[m][0]:
                left_y.append(point)
            elif point[0] > X[m][0]:
                right_y.append(point)
            else:
                left_y.append(point)
                right_y.append(point)
            
        divide(left_x,left_y)
        divide(right_x,right_y)

        get_distance(left_x,left_y,right_x,right_y,m)

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


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

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

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

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

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

dist = 0
dist_min = math.inf

divide(X,Y)

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