数据结构算法分治（两个组的点之间的最小距离）

 ```cpp /*两个组的点之间的最小距离
 暴力复杂度1e10
 将两个组的点都合并之后分治
 将两组点按x坐标递增排序
 分治的关键就是合并的那块：  为什么可以和mid比较进行筛选、   因为两边的最小距离mi已知
 两边的点可能存在两点之和小于mi  也可能不存在
 如果存在  那么这两个点的x取值范围一定在  [mid.x-mi,mid.x=mi]之间
 | .         |
 |    . .    |
 |  .        |
 |        .  |
 | .   .     |
      mid
       |
       |
筛选出的点进行y升序排序  暴力循环  查找每个点到其他点的最短距离和mi取最小(还可以优化  就是两点的y只差大于mi 则两点之间距离肯定大于mi break掉 计算下一个点)

*/ #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<set> #include<queue> #include<cmath> using namespace std; typedef long long ll; ll n; const double INF = 1e48; struct node{ double x,y; bool flag;//标记是否是同组的 }; node a[200005]; node b[200005]; double dis(node a,node b){ if(a.flag==b.flag){ return INF; }else{ return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } } bool cmpy(node a,node b){ return a.y<b.y; } bool cmp(node a,node b){ return a.x<b.x; } double DIS(ll l,ll r){ if(l==r)return INF; if(r-l==1){ return dis(a[l],a[r]); } ll mid = (l + r) / 2; double mi = INF; double lmi = DIS(l,mid); double rmi = DIS(mid+1,r); mi = min(lmi,rmi); ll cnt = 0; for(int i = l; i <= r; i++){//关键的合并筛选 如上图 if(abs(a[i].x-a[mid].x)<=mi){ b[cnt++] = a[i]; } } sort(b,b+cnt,cmpy); for(int i = 0; i < cnt; i++){ for(int j = i+1; j < cnt; j++){ if(abs(b[i].y-b[j].y)>mi)break; mi = min(mi,dis(b[i],b[j])); } } return mi; } int main(){ ios::sync_with_stdio(false); cin.tie(NULL); int t; cin>>t; while(t--){ cin>>n; for(int i = 1; i <= n; i++){ cin>>a[i].x>>a[i].y; a[i].flag = false; } for(int i = 1; i <= n; i++){ cin>>a[i+n].x>>a[i+n].y; a[i].flag = true; } sort(a+1,a+2*n+1,cmp); printf("%.3f\n",DIS(1,2*n)); } return 0; } 

本文地址：https://blog.csdn.net/weixin_43550608/article/details/107757652