C++最近点对算法详解（分治法高效求解平面最近点对问题）

算法核心思想：分治法

分治法求最近点对的基本思路如下：

1. 分解：将所有点按 x 坐标排序，用一条垂直线将点集分为左右两半。
2. 解决：递归地在左半部分和右半部分分别求出最近点对距离，记为 d_left 和 d_right。
3. 合并：取 d = min(d_left, d_right)。但最近点对可能一个在左边、一个在右边！所以我们需要检查跨越中线、且横坐标距离小于 d 的“带状区域”内的点。

关键在于：在带状区域内，每个点只需与它后面最多 6 个点比较（数学可证明），因此合并步骤是线性的。

C++代码实现

下面是一个完整的、可运行的 C++ 实现。我们使用了标准库中的 vector 和 sort，并定义了点结构体。

#include <iostream>#include <vector>#include <algorithm>#include <cmath>#include <climits>using namespace std;struct Point {    double x, y;};// 计算两点间欧氏距离double dist(const Point& p1, const Point& p2) {    return sqrt((p1.x - p2.x) * (p1.x - p2.x) +                 (p1.y - p2.y) * (p1.y - p2.y));}// 按 x 坐标排序的比较函数bool cmpX(const Point& a, const Point& b) {    return a.x < b.x;}// 按 y 坐标排序的比较函数bool cmpY(const Point& a, const Point& b) {    return a.y < b.y;}// 暴力法：当点数较少时直接计算double bruteForce(vector<Point>& points, int left, int right) {    double minDist = DBL_MAX;    for (int i = left; i <= right; ++i) {        for (int j = i + 1; j <= right; ++j) {            minDist = min(minDist, dist(points[i], points[j]));        }    }    return minDist;}// 核心递归函数double closestUtil(vector<Point>& Px, vector<Point>& Py, int n) {    // 如果点太少，直接暴力    if (n <= 3) {        return bruteForce(Px, 0, n - 1);    }    // 分割点    int mid = n / 2;    Point midPoint = Px[mid];    // 将 Py 分成左右两部分（保持 y 有序）    vector<Point> Pyl, Pyr;    for (int i = 0; i < n; ++i) {        if (Py[i].x <= midPoint.x)            Pyl.push_back(Py[i]);        else            Pyr.push_back(Py[i]);    }    // 递归求左右最小距离    double dl = closestUtil(vector<Point>(Px.begin(), Px.begin() + mid), Pyl, mid);    double dr = closestUtil(vector<Point>(Px.begin() + mid, Px.end()), Pyr, n - mid);    double d = min(dl, dr);    // 构建带状区域（strip）    vector<Point> strip;    for (int i = 0; i < n; ++i) {        if (abs(Py[i].x - midPoint.x) < d) {            strip.push_back(Py[i]);        }    }    // 检查 strip 中的点    double minStrip = d;    for (size_t i = 0; i < strip.size(); ++i) {        for (size_t j = i + 1; j < strip.size() &&              (strip[j].y - strip[i].y) < minStrip; ++j) {            minStrip = min(minStrip, dist(strip[i], strip[j]));        }    }    return min(d, minStrip);}// 主函数：对外接口double closestPair(vector<Point>& points) {    int n = points.size();    if (n < 2) return 0.0;    vector<Point> Px = points;    vector<Point> Py = points;    sort(Px.begin(), Px.end(), cmpX);    sort(Py.begin(), Py.end(), cmpY);    return closestUtil(Px, Py, n);}// 测试示例int main() {    vector<Point> points = {{2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4}};    cout << "最近点对距离为: " << closestPair(points) << endl;    return 0;}

代码说明

• 我们维护两个点数组：Px（按 x 排序）和 Py（按 y 排序），避免每次递归都重新排序。
• 当点数 ≤ 3 时，使用暴力法更高效。
• 在带状区域（strip）中，我们只比较 y 坐标差小于当前最小距离 d 的点对，这保证了线性时间。

总结

通过本教程，你已经掌握了如何用 C++ 实现高效的最近点对算法。这种高效最近点对实现不仅适用于学术研究，也广泛应用于实际工程中，如地理信息系统、计算机视觉和机器学习等领域。掌握这一算法，是你迈向高级 C++ 编程和计算几何的重要一步！

记住，算法的核心不是死记硬背，而是理解“分而治之”的思想。多动手写代码、调试、优化，你一定能成为 C++ 算法高手！