题解 | #Raid# 最近点对

模板题，改一改就a了，注意输出格式

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

struct point{
    double x,y;
    int f;
    point():x(0),y(0),f(0){}
};

vector<point> p;
vector<int> a;
int n;

double dis(point a,point b){
    if(a.f != b.f) return sqrt(pow(a.x-b.x,2)+pow(a.y - b.y,2));
    return 0x3f3f3f3f;
}

bool cmp1(point a,point b){
    if (a.x != b.x)return a.x < b.x;
    return a.y < b.y;
}

double near_dis(int l,int r){
    if(r == l + 1) return dis(p[l],p[r]);
    if(l + 2 == r) return min(dis(p[l],p[r]),min(dis(p[l],p[l+1]),dis(p[l+1],p[r])));
    int mid  =( l + r) >> 1;
    double ans = min(near_dis(l,mid),near_dis(mid+1,r));
    a.clear();
    for(int i = l;i <= r;i++)
        if(p[i].x >= p[mid].x - ans && p[i].x <= p[mid].x + ans)
            a.push_back(i);
    for(int i = 0;i < a.size();i++){
        for(int j = i + 1;j<a.size();j++){
            if(abs(p[a[j]].y - p[a[i]].y) >= ans) break;
            ans = min(ans ,dis( p[a[i]],p[a[j]]));
        }
    }
    return ans;
}

int main(){
    int t;cin>>t;
    while(t--){
        cin>>n;
        p.resize(2 * n + 1);
        for(int i = 1;i < p.size();i++) {
            cin>>p[i].x>>p[i].y;
            if(i <= n) p[i].f = 1;
        }
        sort(p.begin()+1,p.end(),cmp1);
        printf("%.3f\n",near_dis(1,2*n));
    }
    return 0;
}