Cod sursa(job #2492469)

Utilizator toni123Mititelu George-Antonio toni123 Data 14 noiembrie 2019 19:59:44
Problema Cele mai apropiate puncte din plan Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 1.99 kb
import math
   
def distance(p1, p2):
    return math.sqrt((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2)

def min_points_dist(points, n):
    minim, i = 1000, 0
    while i<n:
        j = i+1
        while j < n:
            if distance(points[i], points[j]) < minim:
                minim = distance(points[i], points[j])
            j += 1
        i += 1   
    return minim

def strip(points, size, distance_min):
    minim, i = distance_min, 0
    while i<size:
        j = i+1
        while j < size and (points[j][1] - points[i][1]) < minim:
            if distance(points[i], points[j]) < minim:
                minim = distance(points[i], points[j])
            j += 1
        i += 1   
    return minim


def div_conq(sort_by_x, sort_by_y, n):
    if n <= 3:
        return min_points_dist(sort_by_x, n)
    
    mid = n // 2
    mid_point = sort_by_x[mid]
    sort_by_y_left, sort_by_y_right = [], []

    for point in sort_by_y:
        if point[0] < mid_point[0]:
            sort_by_y_left.append(point)
        else:
            sort_by_y_right.append(point)

    distance_left = div_conq(sort_by_x[:mid], sort_by_y_left, mid)
    distance_right = div_conq(sort_by_x[mid:], sort_by_y_right, n-mid)

    distance_min = min(distance_left, distance_right)

    close_points = []
    for point in sort_by_y:
        if abs(point[0] - mid_point[0]) < distance_min:
            close_points.append(point)
    return min(distance_min, strip(close_points, len(close_points), distance_min))

def main():
    points = []
    with open('cmap.in', 'r') as file:
        n = int(file.readline())
        for i in range(n):
            x, y = file.readline().split()
            points.append((int(x), int(y)))

    sort_by_x = sorted(points, key=lambda x: x[0])
    sort_by_y = sorted(points, key=lambda x: x[1])

    minim = div_conq(sort_by_x, sort_by_y, n)
    with open('cmap.out', 'w') as file:
        file.write(str(round(minim, 6)))

if __name__ == "__main__":
    main()