首页 > 代码库 > 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 : 集会