编辑“︁最近点对问题”︁（章节）

== 算法实现 ==
以下是使用Python实现的分治算法：

<syntaxhighlight lang="python">
import math

def closest_pair(points):
    # 预处理：按x坐标排序
    points_sorted_x = sorted(points, key=lambda x: x[0])
    return _closest_pair(points_sorted_x)

def _closest_pair(points):
    n = len(points)
    if n <= 3:
        # 对于小规模问题，直接暴力计算
        return brute_force(points)
    
    mid = n // 2
    mid_point = points[mid]
    
    # 递归处理左右子集
    dl = _closest_pair(points[:mid])
    dr = _closest_pair(points[mid:])
    d = min(dl, dr)
    
    # 收集距离分割线不超过d的点
    strip = [point for point in points if abs(point[0] - mid_point[0]) < d]
    strip_sorted_y = sorted(strip, key=lambda x: x[1])
    
    # 检查带状区域内的点对
    min_strip = d
    for i in range(len(strip_sorted_y)):
        j = i + 1
        while j < len(strip_sorted_y) and (strip_sorted_y[j][1] - strip_sorted_y[i][1]) < min_strip:
            dist = distance(strip_sorted_y[i], strip_sorted_y[j])
            if dist < min_strip:
                min_strip = dist
            j += 1
    
    return min(d, min_strip)

def brute_force(points):
    min_dist = float('inf')
    for i in range(len(points)):
        for j in range(i+1, len(points)):
            dist = distance(points[i], points[j])
            if dist < min_dist:
                min_dist = dist
    return min_dist

def distance(p1, p2):
    return math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)

# 示例输入
points = [(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]
print("最小距离:", closest_pair(points))
</syntaxhighlight>

=== 输入与输出示例 ===
'''输入'''：<code>[(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]</code>  
'''输出'''：<code>最小距离: 1.4142135623730951</code>  
'''解释'''：最近点对是<code>(2, 3)</code>和<code>(3, 4)</code>，其距离为<math>\sqrt{(3-2)^2 + (4-3)^2} = \sqrt{2} \approx 1.414</math>。