```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("%.3fn",DIS(1,2*n)); } return 0; }
c/c++开发分享数据结构算法分治(两个组的点之间的最小距离)地址:https://blog.csdn.net/weixin_43550608/article/details/107757652
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/598292.html