Cod sursa(job #2483961)

Utilizator Sergiu.VictorTalmacel Sergiu Victor Sergiu.Victor Data 30 octombrie 2019 16:26:31
Problema Cele mai apropiate puncte din plan Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 1.82 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(points, key=lambda x: x[1])
    return px, py


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


def base_case(px):
    minim = 10 ** 18
    for i in range(0, len(px) - 1):
        for j in range(i + 1, len(px)):
            dist = compute_distance(px[i], px[j])
            if dist < minim:
                minim = dist
                poz = [i, j]
    return minim


def compute_strip(strip, d):
    minim = d
    for i in range(0, len(strip) - 1):
        for j in range(i + 1, len(strip)):
            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 + 1:], py[mid + 1:])

        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(closest_two_points(px, py)))


if __name__ == "__main__":
    main()