题目传送门
【题目大意】
有$N$个核电站和$N$个特工，均已知坐标，求特工与核电站之间的最短距离。
【思路分析】
平面最近点对板子题，注意特判一下两个点之间的关系，要求的是特工与核电站之间的距离，一共有$2N$个点。
平面最近点对相关知识走链接
【代码实现】
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<algorithm> 5 #define rg register 6 #define go(i,a,b) for(rg int i=a;i<=b;i++) 7 #define db double 8 using namespace std; 9 const int N=200002; 10 const db INF=1e9; 11 int T,n; 12 struct point{ 13 db x,y; 14 bool mark; 15 }p[N]; 16 db D(int a,int b){ 17 db X=p[a].x-p[b].x; 18 db Y=p[a].y-p[b].y; 19 return sqrt(X*X+Y*Y); 20 } 21 bool cmp(point &a,point &b){ 22 if(a.x!=b.x) return a.x<b.x; 23 return a.y<b.y; 24 } 25 bool cm(int &a,int &b){ 26 return p[a].y<p[b].y; 27 } 28 int mid_id[N]; 29 db work(int l,int r){ 30 if(l==r) return INF; 31 if(l+1==r&&p[l].mark==p[r].mark) return INF; 32 if(l+1==r) return D(l,r); 33 int mid=(l+r)/2;db d=INF; 34 db d1=work(l,mid),d2=work(mid+1,r); 35 d=min(d1,d2); 36 int num=0; 37 go(i,l,r) 38 if((db)abs(p[i].x-p[mid].x)<=d) mid_id[++num]=i; 39 sort(mid_id+1,mid_id+1+num,cm); 40 go(i,1,num-1) 41 go(j,i+1,num){ 42 if(p[mid_id[j]].y-p[mid_id[i]].y>=d) break; 43 if(p[mid_id[j]].mark==p[mid_id[i]].mark) continue; 44 db d3=D(mid_id[i],mid_id[j]); 45 d=min(d,d3); 46 } 47 return d; 48 } 49 int main(){ 50 scanf("%d",&T); 51 while(T--){ 52 scanf("%d",&n); 53 go(i,1,n) scanf("%lf%lf",&p[i].x,&p[i].y),p[i].mark=0; 54 go(i,1,n) scanf("%lf%lf",&p[i+n].x,&p[i+n].y),p[i+n].mark=1; 55 sort(p+1,p+1+n*2,cmp); 56 printf("%.3lf\n",work(1,n*2)); 57 } 58 return 0; 59 } 代码戳这里转载于:https://www.cnblogs.com/THWZF/p/11262418.html
