Pagini recente » Cod sursa (job #782599) | Cod sursa (job #899486) | Cod sursa (job #769389) | Cod sursa (job #1963700) | Cod sursa (job #3349527)
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()