import math
def dist(p1, p2):
return math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)
def closest_split_pair(p_x, p_y, delta, best_pair):
ln_x = len(p_x) # store length - quicker
mx_x = p_x[ln_x // 2][0] # select midpoint on x-sorted array # Create a subarray of points not further than delta from
# midpoint on x-sorted array
s_y = [x for x in p_y if mx_x - delta <= x[0] <= mx_x + delta]
best = delta # assign best value to delta
ln_y = len(s_y) # store length of subarray for quickness
for i in range(ln_y - 1):
for j in range(i+1, min(i + 7, ln_y)):
p, q = s_y[i], s_y[j]
dst = dist(p, q)
if dst < best:
best_pair = p, q
best = dst
return best_pair[0], best_pair[1], best
def brute(points):
minim = 9e18
for i in range(len(points)):
for j in range(i + 1, len(points)):
d = dist(points[i], points[j])
if d < minim:
minim = d
p1, p2 = points[i], points[j]
return p1, p2, minim
def closest_pair(ax, ay):
ln_ax = len(ax)
if ln_ax <= 3:
return brute(ax)
mid = ln_ax // 2
Qx = ax[:mid]
Rx = ax[mid:]
midpoint = ax[mid][0]
Qy = list()
Ry = list()
for x in ay:
if x[0] <= midpoint:
Qy.append(x)
else:
Ry.append(x)
(p1, q1, mi1) = closest_pair(Qx, Qy)
(p2, q2, mi2) = closest_pair(Rx, Ry)
if mi1 <= mi2:
d = mi1
mn = (p1, q1)
else:
d = mi2
mn = (p2, q2)
(p3, q3, mi3) = closest_split_pair(ax, ay, d, mn)
if d <= mi3:
return mn[0], mn[1], d
else:
return p3, q3, mi3
def main():
#points = [ (2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]
#points = [(26, 77), (12, 37), (14, 18), (19, 96), (71, 95), (91, 9), (98, 43), (66, 77), (2, 75), (94, 91)]
f = open("cmap.in", "r")
g = open("cmap.out", "w")
n = int(f.readline())
text = f.read()
text = [item.split() for item in text.split('\n')[:n+1]]
points = []
for i in text:
points.append((int(i[0]), int(i[1])))
px = sorted(points, key=lambda x: x[0])
py = sorted(points, key=lambda x: x[1])
p1, p2, mi = closest_pair(px, py) # Recursive D&C function
g.write("{0:.6f}".format(mi))
if __name__ == "__main__":
main()