[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;
}