Cod sursa(job #3349527)

Utilizator tudcellTudor Sabau tudcell Data 31 martie 2026 10:57:36
Problema Cele mai apropiate puncte din plan Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 1.69 kb
import math
import sys

sys.setrecursionlimit(200000)

def dist2(a, b):
    dx = a[0] - b[0]
    dy = a[1] - b[1]
    return dx * dx + dy * dy

def closest_pair(px):
    n = len(px)

    if n <= 3:
        ans = float("inf")
        py = sorted(px, key=lambda p: p[1])
        for i in range(n):
            for j in range(i + 1, n):
                ans = min(ans, dist2(px[i], px[j]))
        return ans, py

    mid = n // 2
    mid_x = px[mid][0]

    left = px[:mid]
    right = px[mid:]

    d_left, py_left = closest_pair(left)
    d_right, py_right = closest_pair(right)

    d = min(d_left, d_right)

    py = []
    i = j = 0
    while i < len(py_left) and j < len(py_right):
        if py_left[i][1] <= py_right[j][1]:
            py.append(py_left[i])
            i += 1
        else:
            py.append(py_right[j])
            j += 1

    while i < len(py_left):
        py.append(py_left[i])
        i += 1

    while j < len(py_right):
        py.append(py_right[j])
        j += 1

    strip = []
    for p in py:
        if (p[0] - mid_x) * (p[0] - mid_x) < d:
            strip.append(p)

    m = len(strip)
    for i in range(m):
        j = i + 1
        while j < m and (strip[j][1] - strip[i][1]) * (strip[j][1] - strip[i][1]) < d:
            d = min(d, dist2(strip[i], strip[j]))
            j += 1

    return d, py

def solve():
    with open("cmap.in", "r") as fin:
        n = int(fin.readline())
        points = [tuple(map(int, fin.readline().split())) for _ in range(n)]

    points.sort()  # sortare după x, apoi după y

    ans2, _ = closest_pair(points)
    ans = math.sqrt(ans2)

    with open("cmap.out", "w") as fout:
        fout.write(f"{ans:.6f}\n")

if __name__ == "__main__":
    solve()