AC

资本  •  11天前


include <bits/stdc++.h>

using namespace std;

define int long long

int n; struct point{

double x;
double y;

}pl[1000010]; bool cmpx(point p1,point p2){

return p1.x<p2.x;

} bool cmpy(point p1,point p2){

return p1.y<p2.y;

} double dis(point p1,point p2){

return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));

} double ans=1e18; double solve(int left,int right){

if(left==right) return 1e18;
int mid=(left+right)/2;
double ans=min(solve(left,mid),solve(mid+1,right));
vector<point> p;
for(int i=mid;i>=left;i--){
	if(pl[mid].x-pl[i].x<=ans){
		p.push_back(pl[i]);
	}
}
for(int i=mid+1;i<=right;i++){
	if(pl[i].x-pl[mid].x<=ans){
		p.push_back(pl[i]);
	}
}
sort(p.begin(),p.end(),cmpy);
for(int i=0;i<p.size();i++){
	for(int j=i+1;j<p.size()&&p[j].y-p[i].y<ans;j++){
		ans=min(ans,dis(p[i],p[j]));
	}
}
return ans;

} signed main(){ // freopen(".in","r",stdin); // freopen(".out","w",stdin);

cin>>n;
for(int i=1;i<=n;i++){
	cin>>pl[i].x;
}
for(int i=1;i<=n;i++){
	cin>>pl[i].y;
}
sort(pl+1,pl+n+1,cmpx);
cout<<fixed<<setprecision(4)<<solve(1,n);

// fclose(stdin); // fclose(stdout);

return 0;

}


评论:

请先登录,才能进行评论