import math
from itertools import combinations
file_in = open("cmap.in", "r")
file_out = open("cmap.out", "w")
def dist(p1, p2):
return (p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2
def bruteForce(Px):
p1=Px[0]
p2=Px[1]
distP=dist(p1,p2)
len_Px=len(Px)
if len_Px==2:
return p1, p2, distP
for x, y in combinations(Px,2):
z=dist(x,y)
if z<distP:
distP=z
p1,p2=x,y
return p1, p2, distP
def closestLR(P_x, P_y, distP, bestpair):
len_Px = len(P_x)
len_Py = len(P_y)
mid = len_Px // 2
midx = P_x[mid][0]
bestdist=distP
for i in range(len_Py - 1):
for j in range(i + 1, min(i + 7, len_Py)):
p, q = P_y[i], P_y[j]
dst = dist(p, q)
if dst < bestdist:
bestpair = [p, q]
bestdist = dst
return bestpair[0], bestpair[1], bestdist
def closestTwo(Px, Py):
len_Px = len(Px)
if len_Px<=3:
return bruteForce(Px)
mid = len_Px // 2
Lx = Px[:mid]
Rx = Px[mid:]
midx = Px[mid][0]
Ly = []
Ry = []
for point in Py:
if point[0] < midx:
Ly.append(point)
else:
Ry.append(point)
l1, l2, distL = closestTwo(Lx, Ly)
r1, r2, distR = closestTwo(Rx, Ry)
bestdist=0
bestpair=[]
if distL<distR:
bestdist=distL
bestpair=[l1,l2]
else:
bestdist=distR
bestpair=[r1,r2]
p1, p2, distLR = closestLR(Px,Py,bestdist, bestpair)
if distLR<bestdist:
return p1,p2, distLR
else:
return bestpair[0], bestpair[1], bestdist
points = []
n = int(file_in.readline())
for line in file_in.readlines():
line = [int(i) for i in line.split()]
points.append(line)
Px = sorted(points, key=lambda x: x[0])
Py = sorted(points, key=lambda x: (x[1],x[0]))
p1, p2, d = closestTwo(Px, Py)
# print(round(math.sqrt(d),6))
file_out.write("%f\r" % round(math.sqrt(d),6))