分治点对距离最短用py写出相关代码

以下是使用 Python 实现的分治点对距离最短算法的代码：

import math

def distance(p1, p2):
    """
    计算两个点之间的欧几里得距离
    """
    return math.sqrt((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2)

def closest_pair(points):
    """
    分治点对距离最短算法
    """
    n = len(points)
    if n <= 1:
        return float('inf')
    elif n == 2:
        return distance(points[0], points[1])
    
    # 将所有点按照横坐标排序
    sorted_points = sorted(points, key=lambda x: x[0])
    mid = n // 2
    left_points = sorted_points[:mid]
    right_points = sorted_points[mid:]
    
    # 递归求解左右两边的最短距离
    left_min_distance = closest_pair(left_points)
    right_min_distance = closest_pair(right_points)
    
    # 计算跨越中线的点对的最短距离
    min_distance = min(left_min_distance, right_min_distance)
    mid_point = sorted_points[mid]
    strip_points = [point for point in sorted_points if abs(point[0]-mid_point[0]) < min_distance]
    strip_points.sort(key=lambda x: x[1])
    strip_n = len(strip_points)
    for i in range(strip_n - 1):
        for j in range(i+1, min(i+8, strip_n)):
            d = distance(strip_points[i], strip_points[j])
            if d < min_distance:
                min_distance = d
    
    return min_distance

这段代码中，我们先定义了计算两个点之间欧几里得距离的函数 distance。然后，我们使用递归的方式来求解分治点对距离最短问题。在递归的过程中，我们首先将所有点按照横坐标排序，然后将它们平分成左右两个集合，分别求出左右两边的最短距离。接着，我们计算跨越中线的点对的最短距离，如果有更小的距离，则更新最短距离的值。最后返回最终的最短距离值。