Pagini recente » Cod sursa (job #2973945) | Cod sursa (job #1592753) | Borderou de evaluare (job #1036666) | Cod sursa (job #451239) | Cod sursa (job #2492469)
import math
def distance(p1, p2):
return math.sqrt((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2)
def min_points_dist(points, n):
minim, i = 1000, 0
while i<n:
j = i+1
while j < n:
if distance(points[i], points[j]) < minim:
minim = distance(points[i], points[j])
j += 1
i += 1
return minim
def strip(points, size, distance_min):
minim, i = distance_min, 0
while i<size:
j = i+1
while j < size and (points[j][1] - points[i][1]) < minim:
if distance(points[i], points[j]) < minim:
minim = distance(points[i], points[j])
j += 1
i += 1
return minim
def div_conq(sort_by_x, sort_by_y, n):
if n <= 3:
return min_points_dist(sort_by_x, n)
mid = n // 2
mid_point = sort_by_x[mid]
sort_by_y_left, sort_by_y_right = [], []
for point in sort_by_y:
if point[0] < mid_point[0]:
sort_by_y_left.append(point)
else:
sort_by_y_right.append(point)
distance_left = div_conq(sort_by_x[:mid], sort_by_y_left, mid)
distance_right = div_conq(sort_by_x[mid:], sort_by_y_right, n-mid)
distance_min = min(distance_left, distance_right)
close_points = []
for point in sort_by_y:
if abs(point[0] - mid_point[0]) < distance_min:
close_points.append(point)
return min(distance_min, strip(close_points, len(close_points), distance_min))
def main():
points = []
with open('cmap.in', 'r') as file:
n = int(file.readline())
for i in range(n):
x, y = file.readline().split()
points.append((int(x), int(y)))
sort_by_x = sorted(points, key=lambda x: x[0])
sort_by_y = sorted(points, key=lambda x: x[1])
minim = div_conq(sort_by_x, sort_by_y, n)
with open('cmap.out', 'w') as file:
file.write(str(round(minim, 6)))
if __name__ == "__main__":
main()