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):
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:]
# calculate minimum distance in the left part and in the right part
ds = distanta(len(xs), xs)
dd = distanta(len(xd), xd)
# calculate the minimum distance in both parts
d = min_punct(ds, dd)
# form the band
band = []
for i in range(n):
if x[i][0] >= (middle - d[0]) and x[i][0] <= (middle + d[0]):
band.append(x[i])
band.sort(key=itemgetter(1))
# calculate distances between points situated in the band
for i in range(len(band) - 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)
fw = open("cmap.out", "w")
fw.write(str(p[0]))
fw.close()