分治法求最近点数问题代码

最近点对问题是求平面上一组点中距离最近的两个点，可以使用分治法来解决。以下是使用C++实现的代码：

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

struct Point {
    double x, y;

    Point() {}

    Point(double x, double y) : x(x), y(y) {}
};

// 按照x坐标排序
bool cmp_x(const Point &a, const Point &b) {
    return a.x < b.x;
}

// 按照y坐标排序
bool cmp_y(const Point &a, const Point &b) {
    return a.y < b.y;
}

// 计算两点之间的距离
double dist(const Point &a, const Point &b) {
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}

// 分治求解最近点对
double closest_pair(vector<Point> &points, int left, int right) {
    if (right - left <= 3) {
        // 当点数小于等于3时直接暴力求解
        double d = 1e9;
        for (int i = left; i <= right; i++) {
            for (int j = i + 1; j <= right; j++) {
                d = min(d, dist(points[i], points[j]));
            }
        }
        return d;
    }

    int mid = (left + right) >> 1;
    double d1 = closest_pair(points, left, mid); // 左侧最小距离
    double d2 = closest_pair(points, mid + 1, right); // 右侧最小距离
    double d = min(d1, d2);

    vector<Point> strip;
    for (int i = left; i <= right; i++) {
        if (fabs(points[i].x - points[mid].x) < d) {
            strip.push_back(points[i]);
        }
    }

    sort(strip.begin(), strip.end(), cmp_y);

    int len = strip.size();
    for (int i = 0; i < len; i++) {
        for (int j = i + 1; j < len && strip[j].y - strip[i].y < d; j++) {
            d = min(d, dist(strip[i], strip[j]));
        }
    }

    return d;
}

int main() {
    int n;
    cin >> n;

    vector<Point> points(n);
    for (int i = 0; i < n; i++) {
        cin >> points[i].x >> points[i].y;
    }

    sort(points.begin(), points.end(), cmp_x);

    double ans = closest_pair(points, 0, n - 1);
    cout << ans << endl;

    return 0;
}

该代码的时间复杂度为O(n log n)，其中n为点的数量。