Pagini recente » Cod sursa (job #3181100) | Cod sursa (job #2630471) | Cod sursa (job #265649) | Cod sursa (job #3142810) | Cod sursa (job #2491810)
from operator import itemgetter
import math
def distance_2(point1, point2):
return (point1[0] - point2[0]) * (point1[0] - point2[0]) + (point1[1] - point2[1]) * (point1[1] - point2[1])
def divide(st, dr):
if dr - st <= 3:
dist = math.inf
for i in range(st, dr+1):
for j in range(i+1, dr+1):
dist = min(dist,distance_2(X[i],X[j]))
return dist
m = st + (dr - st) // 2
dist_s = divide(st,m)
dist_d = divide(m+1,dr)
dist_min = min(dist_s,dist_d)
band = []
for i in range(st,dr+1):
if (abs(X[m][0] - X[i][0]) < dist_min):
band.append(X[i])
band.sort(key = itemgetter(1))
for i in range(len(band) - 7):
for j in range(1,8):
dist = distance_2(band[i],band[i+j])
if dist < dist_min:
dist_min = dist
return dist_min
fin = open("cmap.in","r")
text = fin.read()
lines = text.split("\n")
fin.close()
n = int(lines[0])
X = []
for i in range(n):
x,y = lines[i+1].split()
X.append((int(x),int(y)))
X.sort(key = itemgetter(0))
dist_min = math.sqrt(divide(0,len(X) - 1))
fout = open("cmap.out","w")
fout.write("%.6f" % dist_min)
fout.close()