社区讨论

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

P7883平面最近点对(加强加强版)参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lw83eqry
此快照首次捕获于
2024/05/16 01:25
2 年前
此快照最后确认于
2024/05/16 16:23
2 年前
查看原帖
你估计和我一样对于合并时的左右的端点采用的是二分的写法
CPP
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错误吗

回复

0 条回复,欢迎继续交流。

正在加载回复...