为什么会RE

P1429 平面最近点对(加强版)

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);
}

|