from operator import itemgetter
import math
f = open("cmap.in", "r")
if f.mode == 'r':
f1 = f.readlines()
f.close()
n = int((f1[0].split())[0])
x = []
for i in range(n):
line = f1[i+1].split()
x.append([int(line[0]), int(line[1])])
y = sorted(x, key=itemgetter(1))
x.sort(key=itemgetter(0))
def min_punct(ds, dd):
if ds[0] < dd[0]:
return ds
else:
return dd
def distanta(n, x, y):
if n == 2:
return [math.sqrt(pow(x[0][0] - x[1][0], 2) + pow(x[0][1] - x[1][1], 2)), x[0][0], x[0][1], x[1][0], x[1][1]]
elif n == 3:
vmin = [math.sqrt(pow(x[0][0] - x[1][0], 2) + pow(x[0][1] - x[1][1], 2)), x[0][0], x[0][1], x[1][0], x[1][1]]
if math.sqrt(pow(x[0][0] - x[2][0], 2) + pow(x[0][1] - x[2][1], 2)) < vmin[0]:
vmin = [math.sqrt(pow(x[0][0] - x[2][0], 2) + pow(x[0][1] - x[2][1], 2)), x[0][0], x[0][1], x[2][0], x[2][1]]
if math.sqrt(pow(x[1][0] - x[2][0], 2) + pow(x[1][1] - x[2][1], 2)) < vmin[0]:
vmin = [math.sqrt(pow(x[1][0] - x[2][0], 2) + pow(x[1] [1] - x[2][1], 2)), x[1][0], x[1][1], x[2][0], x[2][1]]
return vmin
else:
middle = n//2
# divide points in two parts: left and right
xs, xd = x[:middle+1], x[middle:]
ys, yd = [], []
for i in range(n):
if y[i][0] < x[middle][0]:
ys.append(y[i])
elif y[i][0] > x[middle][0]:
yd.append(y[i])
else:
ys.append(y[i])
yd.append(y[i])
# calculate minimum distance in the left part and in the right part
ds = distanta(len(xs), xs, ys)
dd = distanta(len(xd), xd, yd)
# calculate the minimum distance in both parts
d = min_punct(ds, dd)
# form the band
band = []
for i in range(n):
if y[i][0] >= (middle - d[0]) and y[i][1] <= (middle + d[0]):
band.append(y[i])
# calculate distances between points situated in the band
band_len = len(band)
for i in range(band_len - 7):
for j in range(i+1, i+8):
dist = math.sqrt(
pow(band[i][0] - band[j][0], 2) + pow(band[i][1] - band[j][1], 2))
if dist < d[0]:
d[0] = dist
d[1], d[2] = band[i][0], band[i][1]
d[3], d[4] = band[j][0], band[j][1]
return d
p = distanta(n, x, y)
fw = open("cmap.out", "w")
fw.write(str(p[0]))
fw.close()