Cod sursa(job #2486378)

Utilizator Sergiu.VictorTalmacel Sergiu Victor Sergiu.Victor Data 2 noiembrie 2019 19:42:41
Problema Cele mai apropiate puncte din plan Scor 10
Compilator py Status done
Runda Arhiva educationala Marime 1.81 kb
def read_input():
    points = []
    with open("cmap.in", "r") as fin:
        n = int(fin.readline())
        for _ in range(0, n):
            point = [int(x) for x in fin.readline().split()]
            points.append(point)
    px = sorted(points, key=lambda x: x[0])
    py = sorted(px, key=lambda x: x[1])
    return px, py


def compute_distance(A, B):
    return (A[0] - B[0]) ** 2 + (A[1] - B[1]) ** 2


def base_case(px):
    minim = 4 ** 18
    if len(px) == 3:
        return min(compute_distance(px[0], px[1]), compute_distance(px[0], px[2]),
                   compute_distance(px[1], px[2]))
    elif len(px) == 2:
        return compute_distance(px[0], px[1])
    return minim


def compute_strip(strip, d):
    minim = d
    for i in range(0, len(strip) - 6):
        for j in range(i + 1, i + 7):
            # if abs(strip[i][1] - strip[j][1]) > d:
            #     break
            # else:
            dist = compute_distance(strip[i], strip[j])
            if dist < minim:
                minim = dist
    return minim


def closest_two_points(px, py):
    if len(px) <= 3:
        return base_case(px)
    else:
        mid = (len(px)) // 2

        d_left = closest_two_points(px[:mid], py[:mid])
        d_right = closest_two_points(px[mid:], py[mid:])

        d = min(d_left, d_right)

        # selectez elementele din (M-d,M+d) crescator dupa coordonata y

        strip = []
        for punct in py:
            if abs(punct[0] - px[mid][0]) <= d:
                strip.append(punct)

        return min(d, compute_strip(strip, d))


def main():
    px, py = read_input()
    print(px)
    print(py)
    with open("cmap.out", 'w') as fout:
        fout.write(str((round(closest_two_points(px, py) ** (1 / 2), 6))))


if __name__ == "__main__":
    main()