算法1

(分治) $O(nlogn)$

时间复杂度

O(nlogn)

参考文献

https://www.acwing.com/solution/content/15774/
https://www.acwing.com/problem/content/video/121/

C++ 代码

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

struct Point {
    double x;
    double y;
    bool type;
    Point(double ax, double ay, bool at):
            x(ax), y(ay), type(at) {}
};

const double inf = 1e10;
double dist(Point p1, Point p2) {
    if (p1.type == p2.type) return inf;
    double dx = p1.x - p2.x;
    double dy = p1.y - p2.y;
    return sqrt(dx * dx + dy * dy);
}

auto cmp = [](const Point &p1, const Point &p2) {
    if (p1.x != p2.x) return p1.x < p2.x;
    return p1.y < p2.y;
};
auto cmpX = [](const Point &p1, const Point &p2) { return p1.x < p2.x; };
auto cmpY = [](const Point &p1, const Point &p2) { return p1.y < p2.y; };

double closestPair(vector<Point> &pointsVec, int sIdx, int eIdx) {
    if (eIdx == sIdx) return inf;
    else if (eIdx - sIdx == 1) return dist(pointsVec[sIdx], pointsVec[eIdx]);
    int mid = (sIdx + eIdx) / 2;
    double lRes = closestPair(pointsVec, sIdx, mid);
    double rRes = closestPair(pointsVec, mid + 1, eIdx);
    double minRes = min(lRes, rRes);
    double mid_x = pointsVec[mid].x;

    {
        vector<Point> tmp;
        int i = sIdx, j = mid + 1;
        while (i <= mid && j <= eIdx) {
            if (pointsVec[i].y <= pointsVec[j].y) {
                tmp.push_back(pointsVec[i]);
                i += 1;
            } else {
                tmp.push_back(pointsVec[j]);
                j += 1;
            }
        }
        while (i <= mid) tmp.push_back(pointsVec[i++]);
        while (j <= eIdx) tmp.push_back(pointsVec[j++]);
        for (int k = 0; k < tmp.size(); k += 1) {
            pointsVec[sIdx + k] = tmp[k];
        }
    }

    vector<Point> midVec;
    for (int i = sIdx; i <= eIdx; i += 1) {
        auto p = pointsVec[i];
        if (mid_x - minRes <= p.x && p.x <= mid_x + minRes) {
            midVec.push_back(p);
        }
    }

    for (int i = 0; i + 1 < midVec.size(); i += 1) {
        for (int j = 0; j < 6 && i + j + 1 < midVec.size(); j += 1) {
            double d = dist(midVec[i], midVec[i + j + 1]);
            minRes = min(d, minRes);
        }
    }
    return minRes;
}

int main() {
    int t; scanf("%d", &t);
    for (int i = 0; i < t; i += 1) {
        int n; scanf("%d", &n);
        vector<Point> pointsVec;
        for (int j = 0; j < 2 * n; j += 1) {
            double x, y;
            scanf("%lf%lf", &x, &y);
            pointsVec.push_back(Point(x, y, j < n));
        }
        sort(pointsVec.begin(), pointsVec.end(), cmpX);
        printf("%.3f\n", closestPair(pointsVec, 0, 2 * n - 1));
    }
    return 0;
}