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()