Pagini recente » Cod sursa (job #1632844) | Cod sursa (job #1512914) | Cod sursa (job #2435313) | Cod sursa (job #2174042) | Cod sursa (job #2492232)
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(X):
if len(X) > 3:
m = len(X) // 2
dist_left = divide(X[:m+1])
dist_right = divide(X[m:])
dist_min = min(dist_left,dist_right)
band = []
i = m - 1
while (i >= 0 and X[i][0] > X[m][0] - dist_min):
band.append(X[i])
i -= 1
i = m + 1
while (i < len(X) and X[i][0] < X[m][0] + dist_min):
band.append(X[i])
i += 1
# for i in range(len(X)):
# 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
else:
dist = math.inf
for i in range(len(X)):
for j in range(i+1, len(X)):
dist = min(dist,distance_2(X[i],X[j]))
return dist
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)))
# sort points on x
X.sort(key = itemgetter(0))
dist_min = math.sqrt(divide(X))
fout = open("cmap.out","w")
fout.write("%.6f" % dist_min)
fout.close()