Pagini recente » Cod sursa (job #1341083) | Cod sursa (job #2674789) | Cod sursa (job #1892) | Cod sursa (job #1987064) | Cod sursa (job #2488197)
import math
def dist(point1, point2):
return math.sqrt((point1[0] - point2[0]) ** 2 + (point1[1] - point2[1]) ** 2)
def merge(left_index, mid_index, right_index):
i, j = left_index, mid_index
aux = []
while i < mid_index and j < right_index:
if points[i][0] < points[j][0]:
aux.append(points[i])
i += 1
else:
aux.append(points[j])
j += 1
aux += points[i:mid_index]
aux += points[j:right_index]
for idx in range(len(aux)):
points[left_index + idx] = aux[idx]
def closest_points(left_index, right_index):
if left_index >= right_index:
return 999999999
if left_index - right_index == 1:
merge(left_index, left_index, right_index)
return dist(points[left_index], points[right_index])
mid_index = left_index + (right_index - left_index) // 2
mid_value = points[mid_index][0]
current_best = min(closest_points(left_index, mid_index), closest_points(mid_index + 1, right_index))
merge(left_index, mid_index, right_index)
aux = []
for i in range(left_index, right_index):
if abs(points[i][0] - mid_value) <= current_best:
aux.append(points[i])
for i in range(len(aux)):
for j in range(i + 1, len(aux)):
if j - i < 8:
current_best = min(current_best, dist(aux[i], aux[j]))
else:
break
return current_best
points = []
with open("cmap.in") as file_in:
cnt_points = file_in.readline()
for line in file_in:
x, y = map(int, line.split())
points.append((x, y))
points.sort()
with open("cmap.out", "w") as file_out:
print(closest_points(0, len(points)), file=file_out)