uesn @ 2022-11-22 19:52:42
线下对拍没问题 为什么会RE
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=3e5+10;
const double eps=1e-5;
int n;
struct node{
int x,y,type;
};
node num[N],a[N],c[N],lefta[N],righta[N];
bool cmp(node x,node y){
return x.x<y.x;
}
bool cmp2(node x,node y){
return x.x<y.x;
}
double jl(int i,int j){
return sqrt(pow(lefta[i].x-righta[j].x,2)+pow(lefta[i].y-righta[j].y,2));
}
double dfs(int l,int r){
if(l==r)return 1e9;
int mid=l+r>>1;
int midx=num[mid].x;
double ans=min(dfs(l,mid),dfs(mid+1,r));
int m=0,g=0;
for(int i=l;i<=mid;i++){
if(abs(a[i].x-midx)-eps<=ans)lefta[++m]=a[i];
}
for(int i=mid+1;i<=r;i++){
if(abs(a[i].x-midx)-eps<=ans)righta[++g]=a[i];
}
// if(l==1&&r==n){
// cout<<lefta[4].x<<' '<<lefta[4].y<<endl;
// cout<<righta[2].x<<' '<<righta[2].y<<endl;
// }
int ll=l,rr=mid+1,cnt=l-1;
while(ll<=mid&&rr<=r){
if(a[ll].y<a[rr].y){
c[++cnt]=a[ll];
ll++;
}
else{
c[++cnt]=a[rr];
rr++;
}
}
while(ll<=mid){
c[++cnt]=a[ll];
ll++;
}
while(rr<=r){
c[++cnt]=a[rr];
rr++;
}
for(int i=l;i<=r;i++)a[i]=c[i];
int h=1;
for(int i=1;i<=m;i++){
while(lefta[i].y-righta[h].y>ans)h++;
for(int j=h;j<h+6;j++){
if(j>g)break;
ans=min(ans,jl(i,j));
// if(i==3)cout<<j<<endl;
}
}
return ans;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++){
cin>>num[i].x>>num[i].y;
a[i]=num[i];
}
sort(num+1,num+n+1,cmp);
sort(a+1,a+n+1,cmp);
double ans=dfs(1,n);
printf("%0.4lf\n",ans);
}