Cod sursa(job #2488197)

Utilizator danyvsDan Castan danyvs Data 6 noiembrie 2019 13:37:53
Problema Cele mai apropiate puncte din plan Scor 10
Compilator py Status done
Runda Arhiva educationala Marime 1.77 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[i][0] < points[j][0]:
            aux.append(points[i])
            i += 1
        else:
            aux.append(points[j])
            j += 1

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

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


def closest_points(left_index, right_index):
    if left_index >= right_index:
        return 999999999

    if left_index - right_index == 1:
        merge(left_index, left_index, right_index)
        return dist(points[left_index], points[right_index])

    mid_index = left_index + (right_index - left_index) // 2
    mid_value = points[mid_index][0]

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

    merge(left_index, mid_index, right_index)

    aux = []
    for i in range(left_index, right_index):
        if abs(points[i][0] - mid_value) <= current_best:
            aux.append(points[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 = []
with open("cmap.in") as file_in:
    cnt_points = file_in.readline()
    for line in file_in:
        x, y = map(int, line.split())
        points.append((x, y))
points.sort()

with open("cmap.out", "w") as file_out:
    print(closest_points(0, len(points)), file=file_out)