[COI2007] Sabor

下面给出这道一脸不可做的题的鬼畜性质：
1）对于一个点来说，其归属状态是确定的：走不到、A党或B党 。（黑白格染色）
方便起见，将包含所有不可达的点的极小矩形向外扩展一圈，设为矩形M。
2）矩形M的最外圈上相邻两点点到(0,0)的最短曼哈顿距离差值不超过1。
3）矩形M外任意正对于矩形M的点到垂直走向所正对的边必是到(0,0)的满足曼哈顿距离最小的路径的一条。
4）矩形M外任意非正对于矩形M到最靠近的M的一角必是到(0,0)的满足曼哈顿距离最小的路径的一条。

利用这些性质就可做了。。主要是向外扩展一圈这儿。。

然后就是找找规律的事儿了。。

#include <bits/stdc++.h>
#define P 1000
using namespace std;
const int fx[]={1,-1,0,0};
const int fy[]={0,0,1,-1};

int B,S;
long long cnt[2];
int dis[2005][2005];
int maxx,maxy,minx,miny;
queue<int> Qx,Qy;

inline void f1(int x,int y) {
    cnt[(x+y)&1]+=1LL*((S-dis[x][y])/2)*((S-dis[x][y])/2);
    cnt[(x+y+1)&1]+=1LL*((S-dis[x][y]-1)/2)*((S-dis[x][y]-1)/2+1);
} 
inline void f2(int x,int y) {
    cnt[(x+y)&1]+=(S-dis[x][y])/2;
    cnt[(x+y+1)&1]+=(S-dis[x][y]+1)/2;
}

int main() {
    scanf("%d%d",&B,&S);
    minx=miny=maxx=maxy=P;
    for(int x,y,i=1; i<=B; ++i) {
        scanf("%d%d",&x,&y);
        x+=P,y+=P;
        dis[x][y]=-1;
        minx=min(minx,x);
        maxx=max(maxx,x);
        miny=min(miny,y);
        maxy=max(maxy,y);
    }
    S++;
    minx--,miny--;
    maxx++,maxy++;
    Qx.push(P);
    Qy.push(P);
    dis[P][P]=1;
    while(!Qx.empty()) {
        int x=Qx.front(); Qx.pop();
        int y=Qy.front(); Qy.pop();
        if((x==minx||x==maxx) && (y==miny||y==maxy)) f1(x,y);
        if((x==minx||x==maxx)) f2(x,y);
        if((y==miny||y==maxy)) f2(x,y);
        cnt[(x+y)&1]++;
        if(dis[x][y]==S) continue;
        for(int nx,ny,k=0; k<4; ++k) {
            nx=x+fx[k];
            ny=y+fy[k];
            if(nx<minx||ny<miny||nx>maxx||ny>maxy||dis[nx][ny]) continue;           
            dis[nx][ny]=dis[x][y]+1;
            Qx.push(nx);
            Qy.push(ny);
        }
    }
    printf("%lld %lld\n",cnt[0],cnt[1]);
    return 0;
}