Cod sursa(job #2488193)

Utilizator danyvsDan Castan danyvs Data 6 noiembrie 2019 13:32:31
Problema Cele mai apropiate puncte din plan Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 1.8 kb
import math


def dist(point1, point2):
    return math.sqrt((point1[0] - point2[0]) ** 2 + (point1[1] - point2[1]) ** 2)


def merge(left_index, mid_index, right_index):
    i, j = left_index, mid_index

    aux = []
    while i < mid_index and j < right_index:
        if points_x[i][0] <= points_x[j][0]:
            aux.append(points_x[i])
            i += 1
        else:
            aux.append(points_x[j])
            j += 1

    aux += points_x[i:mid_index]
    aux += points_x[j:right_index]

    for idx in range(len(aux)):
        points_x[left_index + idx] = aux[idx]


def closest_points(left_index, right_index):
    if right_index - left_index < 2:
        return 999999999

    if left_index - right_index == 2:
        merge(left_index, left_index, right_index)
        return dist(points_x[left_index], points_x[right_index])

    mid_index = left_index + (right_index - left_index) // 2

    current_best = min(closest_points(left_index, mid_index), closest_points(mid_index, right_index))

    merge(left_index, mid_index, right_index)

    aux = []
    for i in range(left_index, right_index):
        if abs(points_y[i][1] - points_x[mid_index][0]) <= current_best:
            aux.append(points_y[i])

    for i in range(len(aux)):
        for j in range(i + 1, len(aux)):
            if j - i < 8:
                current_best = min(current_best, dist(aux[i], aux[j]))
            else:
                break

    return current_best


points_x = []
with open("cmap.in") as file_in:
    cnt_points = int(file_in.readline())
    for line in file_in:
        x, y = map(int, line.split())
        points_x.append((x, y))

points_x.sort()
points_y = points_x
for point in points_y:
    point = (point[1], point[0])

print(closest_points(0, cnt_points))