最接近点对问题c++

最接近点对问题（Closest Pair of Points Problem）是一个经典的计算机科学问题，它的目标是在二维空间中找到两个离得最近的点。在C++中，解决这个问题的一种常见算法是使用分治法或排序后迭代。

一种常见的解决方案是使用双指针技巧，首先将所有的点按照x坐标排序，然后维护两个指针i和j分别指向当前已经检查过的区间两端。每次比较这两个区间的左边界点（p[i]和p[j]），并计算它们之间的距离d。如果这个距离小于已知的最小距离，则更新最小距离，并继续检查区间的内部点。如果左侧点的y坐标大于右侧点的y坐标，就向右移动右指针；反之，向左移动左指针。这样逐次缩小搜索范围，直到遍历完整个数组。

以下是简化版的C++代码：

#include <vector>
#include <algorithm>

double closestPair(std::vector<std::pair<int, int>>& points) {
    std::sort(points.begin(), points.end());
    double min_distance = INT_MAX;
    for (int i = 0; i < points.size(); ++i) {
        // 双指针法：一个固定在i位置，另一个从i+1开始移动
        for (int j = i + 1; j < points.size(); ++j) {
            double distance = points[j].first - points[i].first;
            if (distance * distance < min_distance) {
                min_distance = distance;
            }
        }
    }
    return min_distance;
}