平面上的最接近点对

GitHub跳转原题关系图返回列表

按横坐标分治，并在纵坐标有序的中间条带中只检查常数个后继点。

OJ: luogu

题目 ID: P1257

难度:提高+/省选-

标签:分治计算几何归并python

日期: 2026-07-16 18:28

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

给定平面上的 nn 个点，求任意两点间的最短欧氏距离。

思路

先按横坐标排序，再从中点分治。左右两半分别求出最短距离平方 best，剩下只需检查跨越中线的点对。

递归同时返回当前区间按纵坐标排好的点。用两边的纵坐标序列归并后，只保留横向距离平方小于 best 的条带点。平面装箱性质保证：按纵坐标排列后，每个点只需和后面的至多 7 个点比较。

全程比较距离平方，只在最后输出时开一次平方根，既更快也减少浮点误差。

Python 知识

  • heapq.merge(left_y, right_y, key=...) 可以惰性归并两个已有序序列。
  • 列表推导式非常适合筛出中间条带。
  • strip[i + 1:i + 8] 清楚表达“只看后面 7 个候选点”。
  • math.inf 可作为最小值的初始哨兵，math.sqrt 最后再恢复真实距离。

代码

python
import heapq
import math
import sys


data = iter(map(int, sys.stdin.buffer.read().split()))
n = next(data)
points = sorted((next(data), next(data)) for _ in range(n))


def closest(left, right):
    length = right - left
    if length <= 3:
        best = math.inf
        for i in range(left, right):
            for j in range(i + 1, right):
                dx = points[i][0] - points[j][0]
                dy = points[i][1] - points[j][1]
                best = min(best, dx * dx + dy * dy)
        return sorted(points[left:right], key=lambda point: point[1]), best

    middle = (left + right) // 2
    middle_x = points[middle][0]
    left_y, left_best = closest(left, middle)
    right_y, right_best = closest(middle, right)
    best = min(left_best, right_best)
    ordered_y = list(heapq.merge(left_y, right_y, key=lambda point: point[1]))
    strip = [point for point in ordered_y if (point[0] - middle_x) ** 2 < best]
    for i, (x1, y1) in enumerate(strip):
        for x2, y2 in strip[i + 1:i + 8]:
            if (y2 - y1) ** 2 >= best:
                break
            best = min(best, (x2 - x1) ** 2 + (y2 - y1) ** 2)
    return ordered_y, best


_, distance_squared = closest(0, n)
print(f"{math.sqrt(distance_squared):.4f}")

复杂度

递归每层线性归并，共 O(log⁡n)O(\log n) 层，时间 O(nlog⁡n)O(n\log n)，空间 O(n)O(n)。

总结

最近点对的关键不只是“分成两半”，还要让递归结果按纵坐标有序，才能在线性时间处理跨中线候选。