Pagini recente » Cod sursa (job #1069853) | Cod sursa (job #121333) | Cod sursa (job #1723151) | Cod sursa (job #1571056) | Cod sursa (job #2488019)
from math import sqrt
INF = 1000
puncte = []
with open("cmap.in", 'r') as fin:
n = int(next(fin).split()[0])
for i in range(n):
puncte.append([int(elem) for elem in next(fin).split()])
X = [elem[0] for elem in puncte]
Y = [elem[1] for elem in puncte]
X.sort()
Y.sort()
def dist(x1, y1, x2, y2):
return sqrt((x1-x2)**2 + (y1-y2)**2)
def min_dist(vect, s, f):
if s >= f:
return INF
if f-s == 1:
return dist(vect[s][0], vect[s][1], vect[f][0], vect[f][1])
mij = (s + f)//2
d_s = min_dist(vect, s, mij-1)
d_d = min_dist(vect, mij+1, f)
if d_s < d_d:
d, D = d_s, d_d
else:
d, D = d_d, d_s
y_sort = [elem for elem in vect[s:f+1] if abs(elem[0] - vect[mij][0]) <= d]
y_sort.sort(key=lambda elem: elem[1], reverse=False)
for idx, elem in enumerate(y_sort):
for i in range(1, (len(y_sort)-idx) % 7):
dist_to_test = dist(elem[0], elem[1], y_sort[idx+i][0], y_sort[idx+i][1])
if dist_to_test < d:
d = dist_to_test
return d
with open("cmap.out", 'w') as fout:
print(min_dist(puncte, 0, len(puncte)-1), file=fout)
#print(f"distanta minima rezultata = {min_dist(puncte, 0, len(puncte)-1)}")