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
感谢兄弟