分治法解决最近对问题给出c++语言代码

以下是使用分治法解决最近对问题的 C++ 代码：

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

// 计算两个数的最小距离，其中a[]已排序
double closestInStrip(double strip[], int size, double d) {
    double minDist = d;
    for (int i = 0; i < size; ++i) {
        for (int j = i + 1; j < size && (strip[j] - strip[i] < minDist); ++j) {
            minDist = min(minDist, strip[j] - strip[i]);
        }
    }
    return minDist;
}

// 计算最近点对的距离
double closestPair(double x[], double y[], int n) {
    if (n <= 3) {
        double dist = INFINITY;
        for (int i = 0; i < n; ++i) {
            for (int j = i+1; j < n; ++j) {
                dist = min(dist, sqrt(pow(x[i]-x[j], 2) + pow(y[i]-y[j], 2)));
            }
        }
        return dist;
    }

    int mid = n / 2;
    double midX = x[mid];
    double leftDist = closestPair(x, y, mid);
    double rightDist = closestPair(x+mid, y+mid, n-mid);
    double dist = min(leftDist, rightDist);

    // 计算跨越中线的最近点对的距离
    double strip[n];
    int j = 0;
    for (int i = 0; i < n; ++i) {
        if (abs(x[i] - midX) < dist) {
            strip[j++] = y[i];
        }
    }
    sort(strip, strip+j);
    return min(dist, closestInStrip(strip, j, dist));
}

int main() {
    int n = 6;
    double x[] = {2, 12, 40, 5, 12, 3};
    double y[] = {3, 30, 50, 1, 10, 4};
    sort(x, x+n);
    cout << closestPair(x, y, n) << endl; // 输出 2.82843
    return 0;
}

其中，函数 `closestPair` 采用分治法实现，递归地计算左右两部分的最近点对距离，然后计算跨越中线的最近点对距离。函数 `closestInStrip` 计算给定长度的数组中的最近点对距离。在主函数中，我们随机生成了一组 6 个点，然后调用 `closestPair` 计算最近点对距离。