题解：P10459 Raid

· · 题解

思路

这个题其实就是平面最近点对，除了要求特工与能源的最小距离之外，其他地方都一样（致敬人类智慧）。

所以我们考虑分治做法，分别求出分开点坐标左边与右边的最小值再合并，列出坐标，最后再算出距离。

可定义函数 \operatorname{solve} 进行分治，先对坐标按 x 排序，然后求出小于中间坐标 mid 和大于 mid 的最小值 \min(\operatorname{solve}(l,mid),\operatorname{solve}(mid+1,r))，l，r 分别为本次 \operatorname{solve} 函数执行的下界和上界。

再在 [l,r] 范围内进行枚举，若一点的 x 值与 mid 点的 x 值差小于上面求的最小值，那就用数组记录这个点的序号。

最后，在记录的点中遍历，再找出最小值，返回最小值即可。

与平面最近点对不同的是，它要求特工与能源最小距离而不是任意两点的最小距离，因此我们可以在结构体中定义 f 区分特工与能源，再写一个求距离的函数，判断当且仅当两点的 f 不同时（即一个是特工，一个是能源时）再计算距离，否则返回 1\times 10^{12} 代表不能计算。

code

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define N 200005
const double inf=1e12;
int n,b[N],t;
struct node{
    double x,y;
    int f;
}e[N];
struct edge{
    double x,y;
}tmp[N];
double cal(int i,int j){
    if(e[i].f==e[j].f) return inf;
    return sqrt(pow(e[i].x-e[j].x,2)+pow(e[i].y-e[j].y,2));
}
bool cmp(node a,node b){
    return a.x<b.x;
}
bool cmp2(edge i,edge j){
    return i.y<j.y;
}
double solve(int l,int r){
    if(l>=r) return inf;
    if(l+1==r) return cal(l,r);//sqrt(pow(e[l].x-e[r].x,2)+pow(e[l].y-e[r].y,2));
    int mid=(l+r)/2,cnt=0;
    double t=e[mid].x;
    double d=min(solve(l,mid),solve(mid+1,r));
    for(int i=l;i<=r;i++){
        if(fabs(e[i].x-t)<d){
            b[++cnt]=i;
        }
    }
    sort(b+1,b+cnt+1);
    for(int i=1;i<=cnt;i++){
        for(int j=i+1;j<=cnt&&abs(e[b[j]].y-e[b[i]].y)<=d;j++){
            d=min(d,cal(b[i],b[j]));
        }
    }
    return d;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--){
        cin>>n;
        memset(tmp,0,sizeof(tmp));
        for(int i=1;i<=n;i++){
            cin>>e[i].x>>e[i].y;
            e[i].f=0;
        }
        for(int i=n+1;i<=2*n;i++){
            cin>>e[i].x>>e[i].y;
            e[i].f=1;
        }
        sort(e+1,e+2*n+1,cmp);
        printf("%.3lf\n",solve(1,2*n));
    }
    return 0;
}