资本 • 11天前
using namespace std;
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;
}
评论:
请先登录,才能进行评论