如果你得了149分,只WA #17

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

Lezy233 @ 2024-05-16 01:24:57

你估计和我一样对于合并时的左右的端点采用的是二分的写法

auto solve=[&](auto self,int rtL,int rtR)->ll{ // [rtL,rtR)
        if(rtL==rtR) return LLONG_MAX;
        if(rtR-rtL==1) return pow2(aa[rtL].x-aa[rtR].x)+pow2(aa[rtL].y-aa[rtR].y);
        int mid=rtL+rtR>>1;
        ll r2=std::min(self(self,rtL,mid), self(self,mid,rtR));
        ll r=ceil(sqrt(r2));
        auto L=std::lower_bound(aa.begin()+rtL,aa.begin()+mid,PLL(aa[mid].x-r,-1e7));
        auto R=std::lower_bound(aa.begin()+mid,aa.begin()+rtR,PLL(aa[mid].x+r,-1e7));
        vector<PLL>tt(L,R);
        std::ranges::sort(tt,[](const PLL&a,const PLL&b){
            return a.y<b.y;
        });
        for(int i=0,j=1,m=tt.size();i<m;++i){
            while(j<m && tt[j].y-tt[i].y<r) ++j;
            for(int k=i+1;k<j;++k) r2=std::min(r2, pow2(tt[k].x-tt[i].x)+pow2(tt[k].y-tt[i].y));
        }
        return r2;
    };
    cout<<solve(solve,0,n-1)<<endl;

注意到 std::lower_bound() 获取的第二个迭代器是取不到的,所以那个 R 的二分写法应该改成 auto R=std::lower_bound(aa.begin()+mid,aa.begin()+rtR+1,PLL(aa[mid].x+r,-1e7));

话说真的会有人和我犯一样的rz错误吗


by BigFatDuck @ 2024-08-28 12:19:26

感谢兄弟


|