首页 > 代码库 > BZOJ4039 : 集会
BZOJ4039 : 集会
将曼哈顿距离转化为切比雪夫距离,即:
$|x_1-x_2|+|y_1-y_2|=\max(|(x_1+y_1)-(x_2+y_2)|,|(x_1-y_1)-(x_2-y_2)|)$
那么每个点能接受的范围是一个正方形,对正方形求交,若交集为空那么显然无解。
然后在交对应矩形中三分套三分即可,用二分查找配合前缀和加速查询。
这样有一个问题,就是选出的点不一定是整点,那么只需要在那个点附近枚举整点即可。
时间复杂度$O(n\log n+\log^3n)$。
#include<cstdio>#include<algorithm>using namespace std;typedef long long ll;const int N=100010,K=1;const ll inf=1LL<<60;int n,i;ll D,xl,xr,yl,yr,ans,X,Y;struct P{ll x,y,a,b;}a[N];struct DS{ ll a[N],s[N]; void init(){ sort(a+1,a+n+1); for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i]; } inline ll ask(ll x){ int l=1,r=n,t=0,mid; while(l<=r)if(a[mid=(l+r)>>1]<=x)l=(t=mid)+1;else r=mid-1; return x*(t*2-n)-s[t]*2+s[n]; }}Tx,Ty;inline void read(ll&a){char c;while(!(((c=getchar())>=‘0‘)&&(c<=‘9‘)));a=c-‘0‘;while(((c=getchar())>=‘0‘)&&(c<=‘9‘))(a*=10)+=c-‘0‘;}inline ll dis(ll x,ll y){return Tx.ask(x+y)+Ty.ask(x-y);}inline ll cal(ll x,ll y){ ll t=dis(x,y); if(t<ans)ans=t,X=x,Y=y; return t;}inline ll solvey(ll x,ll yl,ll yr){ ll t=inf,len,m1,m2,s1,s2; while(yl<=yr){ len=(yr-yl)/3; s1=cal(x,m1=yl+len),s2=cal(x,m2=yr-len); if(s1<s2)t=min(t,s1),yr=m2-1;else t=min(t,s2),yl=m1+1; } return t;}inline void solvex(ll xl,ll xr,ll yl,ll yr){ ll len,m1,m2,s1,s2; while(xl<=xr){ len=(xr-xl)/3; s1=solvey(m1=xl+len,yl,yr),s2=solvey(m2=xr-len,yl,yr); if(s1<s2)xr=m2-1;else xl=m1+1; }}int main(){ while(~scanf("%d",&n)){ if(!n)return 0; for(i=1;i<=n;i++){ read(a[i].x),read(a[i].y); a[i].a=a[i].x+a[i].y; a[i].b=a[i].x-a[i].y; } read(D); xl=yl=-inf,xr=yr=inf; for(i=1;i<=n;i++){ xl=max(xl,a[i].a-D); xr=min(xr,a[i].a+D); yl=max(yl,a[i].b-D); yr=min(yr,a[i].b+D); } if(xl>xr||yl>yr){puts("impossible");continue;} for(i=1;i<=n;i++)Tx.a[i]=a[i].x*2,Ty.a[i]=a[i].y*2; Tx.init(),Ty.init(); ans=inf; solvex(xl,xr,yl,yr); ans=inf; for(ll x=X-K;x<=X+K;x++)for(ll y=Y-K;y<=Y+K;y++){ if(x<xl||x>xr)continue; if(y<yl||y>yr)continue; if((x+y)%2)continue; ans=min(ans,dis(x,y)); } printf("%lld\n",ans/2); } return 0;}
BZOJ4039 : 集会
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。