Cod sursa(job #2486421)

Utilizator Sergiu.VictorTalmacel Sergiu Victor Sergiu.Victor Data 2 noiembrie 2019 20:47:20
Problema Cele mai apropiate puncte din plan Scor 10
Compilator py Status done
Runda Arhiva educationala Marime 2.24 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, st, dr):
    minim = 4 ** 18
    if dr - st == 2:
        return min(compute_distance(px[st], px[dr]), compute_distance(px[st], px[st + 1]),
                   compute_distance(px[st + 1], px[dr]))
    elif dr - st == 1:
        return compute_distance(px[st], px[dr])
    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):
            dist = compute_distance(strip[i], strip[j])
            if dist < minim:
                minim = dist
    return minim


def merge(st, m, dr, py):
    i, j = st, m + 1
    temp = []
    while i <= m and j <= dr:
        if py[i][1] < py[j][1]:
            temp.append(py[i])
            i += 1
        else:
            temp.append(py[j])
            j += 1
    while i <= m:
        temp.append(py[i])
        i += 1
    while j <= dr:
        temp.append(py[j])
        j += 1

    for i in range(0, len(temp)):
        py[st + i] = temp[i]


def closest_two_points(px, py, st, dr):
    if dr - st < 3:
        return base_case(px, st, dr)
    else:
        mid = (dr + st) // 2

        d_left = closest_two_points(px, py, st, mid)
        d_right = closest_two_points(px, py, mid, dr)

        d = min(d_left, d_right)
        merge(st, mid, dr, py)
        # selectez elementele din (M-d,M+d) crescator dupa coordonata y

        strip = []
        for i in range(st, dr + 1):
            if abs(py[i][0] - px[mid][0]) <= d:
                strip.append(py[i])

        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, 0, len(px) - 1) ** (1 / 2), 6))))


if __name__ == "__main__":
    main()