社区讨论
如果你得了149分,只WA #17
P7883平面最近点对(加强加强版)参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @lw83eqry
- 此快照首次捕获于
- 2024/05/16 01:25 2 年前
- 此快照最后确认于
- 2024/05/16 16:23 2 年前
你估计和我一样对于合并时的左右的端点采用的是二分的写法
CPPauto 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));回复
共 0 条回复,欢迎继续交流。
正在加载回复...