Pagini recente » Cod sursa (job #210268) | Cod sursa (job #1815950) | Cod sursa (job #1603078) | Cod sursa (job #1464535) | Cod sursa (job #2488193)
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_x[i][0] <= points_x[j][0]:
aux.append(points_x[i])
i += 1
else:
aux.append(points_x[j])
j += 1
aux += points_x[i:mid_index]
aux += points_x[j:right_index]
for idx in range(len(aux)):
points_x[left_index + idx] = aux[idx]
def closest_points(left_index, right_index):
if right_index - left_index < 2:
return 999999999
if left_index - right_index == 2:
merge(left_index, left_index, right_index)
return dist(points_x[left_index], points_x[right_index])
mid_index = left_index + (right_index - left_index) // 2
current_best = min(closest_points(left_index, mid_index), closest_points(mid_index, right_index))
merge(left_index, mid_index, right_index)
aux = []
for i in range(left_index, right_index):
if abs(points_y[i][1] - points_x[mid_index][0]) <= current_best:
aux.append(points_y[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_x = []
with open("cmap.in") as file_in:
cnt_points = int(file_in.readline())
for line in file_in:
x, y = map(int, line.split())
points_x.append((x, y))
points_x.sort()
points_y = points_x
for point in points_y:
point = (point[1], point[0])
print(closest_points(0, cnt_points))