2 条题解
-
0
#include<bits/stdc++.h> using namespace std; const int N=5e5+5; struct node{double x,y;int z;}p[N]; bool cmp(node p1,node p2){if(p1.x!=p2.x)return p1.x<p2.x;else return p1.y<p2.y;} double dis(node p1,node p2){return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));} double solve(int l, int r) { if (l == r) return 1e18; int mid = (l + r) >> 1; double ans = min( solve(l,mid) , solve(mid+1, r) ); int tl = mid, tr = mid; while (tl >= l && p[mid].x - p[tl].x < ans) tl--; tl++; while (tr <= r && p[tr].x - p[mid].x < ans) tr++; tr--; for (int i = tl; i < tr; i++) for (int j = i+1; j <= tr; j++)if(p[i].z != p[j].z) ans =min(ans, dis(p[i], p[j])); return ans; } int main() { int T;scanf("%d",&T); while(T--) { int n;scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%lf%lf",&p[i].x,&p[i].y),p[i].z=0; for(int i=n+1;i<=2*n;i++)scanf("%lf%lf",&p[i].x,&p[i].y),p[i].z=1; sort(p+1,p+2*n+1,cmp); printf("%.3lf\n",solve(1,2*n)); } return 0; }#include<bits/stdc++.h>//by:hansang using namespace std; const int N=110000; const double INF=1e10; //10000000000,比输入数据多一个零 struct node { double x,y; bool type; //标记 }points[N],temp[N]; bool cmp(node n1,node n2){return n1.x<n2.x;} //比较函数,如果像 y总 那样打也可以 double dist(node a,node b) //利用勾股定理计算两个点的距离 { if(a.type==b.type)return INF; double dx=a.x-b.x,dy=a.y-b.y; return sqrt(dx*dx+dy*dy); } double dfs(int l,int r) { if(l>=r)return INF; //正无穷 int mid=(l+r)/2; double mid_x=points[mid].x; double res=min(dfs(l,mid),dfs(mid+1,r)); //开始归并 ,在下面括号里面的 k, i, j 可在外面重新定义 { int k=1,i=l,j=mid+1; while(i<=mid&&j<=r) { if(points[i].y<=points[j].y)temp[k++]=points[i++]; //排序纵坐标,因为横坐标已经排过了 else temp[k++]=points[j++]; } while(i<=mid)temp[k++]=points[i++]; while(j<=r)temp[k++]=points[j++]; for(i=1,j=l;j<=r;i++,j++)points[j]=temp[i]; } //注意下面的 k, i, j 和上面的没有任何关系 int k=1; for(int i=l;i<=r;i++) if(points[i].x>=mid_x-res&&points[i].x<=mid_x+res) //满足要求的拉进数组 temp[k++]=points[i]; for(int i=1;i<=k;i++) for(int j=i-1;j>=1&&temp[i].y-temp[j].y<=res;j--) //第二个要求 res=min(res,dist(temp[i],temp[j])); return res; } int main() { int T;scanf("%d",&T); while(T--) { int n;scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%lf%lf",&points[i].x,&points[i].y); points[i].type=0; //核电站 } for(int i=n+1;i<=2*n;i++) { scanf("%lf%lf",&points[i].x,&points[i].y); points[i].type=1; //特工 } sort(points+1,points+2*n+1,cmp); //记住排序的时候是2n,不然会 TLE 50分 printf("%.3lf\n",dfs(1,2*n)); } return 0; } -
0
huangzheng
LV 6
@ 2025-10-8 16:55:42
#include<bits/stdc++.h> using namespace std; const int N=5e5+5; struct node{double x,y;int z;}p[N]; bool cmp(node p1,node p2){if(p1.x!=p2.x)return p1.x<p2.x;else return p1.y<p2.y;} double dis(node p1,node p2){return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));} double solve(int l, int r) { if (l == r) return 1e18; int mid = (l + r) >> 1; double ans = min( solve(l,mid) , solve(mid+1, r) ); int tl = mid, tr = mid; while (tl >= l && p[mid].x - p[tl].x < ans) tl--; tl++; while (tr <= r && p[tr].x - p[mid].x < ans) tr++; tr--; for (int i = tl; i < tr; i++) for (int j = i+1; j <= tr; j++)if(p[i].z != p[j].z) ans =min(ans, dis(p[i], p[j])); return ans; } int main() { int T;scanf("%d",&T); while(T--) { int n;scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%lf%lf",&p[i].x,&p[i].y),p[i].z=0; for(int i=n+1;i<=2*n;i++)scanf("%lf%lf",&p[i].x,&p[i].y),p[i].z=1; sort(p+1,p+2*n+1,cmp); printf("%.3lf\n",solve(1,2*n)); } return 0; }
#include<bits/stdc++.h>//by:hansang using namespace std; const int N=110000; const double INF=1e10; //10000000000,比输入数据多一个零
struct node { double x,y; bool type; //标记 }points[N],temp[N];
bool cmp(node n1,node n2){return n1.x<n2.x;} //比较函数,如果像 y总 那样打也可以
double dist(node a,node b) //利用勾股定理计算两个点的距离 { if(a.type==b.type)return INF; double dx=a.x-b.x,dy=a.y-b.y; return sqrt(dxdx+dydy); }
double dfs(int l,int r) { if(l>=r)return INF; //正无穷 int mid=(l+r)/2; double mid_x=points[mid].x; double res=min(dfs(l,mid),dfs(mid+1,r)); //开始归并 ,在下面括号里面的 k, i, j 可在外面重新定义 { int k=1,i=l,j=mid+1; while(i<=mid&&j<=r) { if(points[i].y<=points[j].y)temp[k++]=points[i++]; //排序纵坐标,因为横坐标已经排过了 else temp[k++]=points[j++]; } while(i<=mid)temp[k++]=points[i++]; while(j<=r)temp[k++]=points[j++]; for(i=1,j=l;j<=r;i++,j++)points[j]=temp[i]; } //注意下面的 k, i, j 和上面的没有任何关系 int k=1; for(int i=l;i<=r;i++) if(points[i].x>=mid_x-res&&points[i].x<=mid_x+res) //满足要求的拉进数组 temp[k++]=points[i];
for(int i=1;i<=k;i++) for(int j=i-1;j>=1&&temp[i].y-temp[j].y<=res;j--) //第二个要求 res=min(res,dist(temp[i],temp[j])); return res;}
int main() { int T;scanf("%d",&T); while(T--) { int n;scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%lf%lf",&points[i].x,&points[i].y); points[i].type=0; //核电站 }
for(int i=n+1;i<=2*n;i++) { scanf("%lf%lf",&points[i].x,&points[i].y); points[i].type=1; //特工 } sort(points+1,points+2*n+1,cmp); //记住排序的时候是2n,不然会 TLE 50分 printf("%.3lf\n",dfs(1,2*n)); } return 0;}
</p>
- 1