题目大意:
给定n行m列的黑白棋盘如下
给定矩形的左下点x1 y1和右上点x2 y2将这个区域都涂成白色
再给定矩形的左下点x3 y3和右上点x4 y4将这个区域都涂成黑色
求最后棋盘内有分别多少个白格和黑格
本来不怎么想发CF赛时AC的题 但是这题比较特别就想发一下~
为什么特别呢? 因为去年寒假集训的时候 有一道求多个矩形并的面积大小的题oj21547overplanting
当时学了一个矩形切割的方法 后来再也没有遇到什么类似的题
而今天 没错就是今天 终于撞上了hhh (虽然因为不熟悉 赛时小心翼翼地码 用了不少时间
好了说正题
首先因为是黑白相间的棋盘格 那么对于一个已知长宽的矩形 (长宽可由左下和右上的位置得到)
若格数为偶数则黑白格各半 若为奇数则多出的一个的颜色必为左下角那一格的颜色
那么怎么知道左下角的一格(设其位置为(i,j))是什么颜色呢
因为黑白相间的特性 只要判断一下 (i+j)%2 就行 为1是黑色 为0则是白色
此时我们可以得到初始的棋盘有 W 个白格 和 B 个黑格
而涂色时 由于黑色是后涂的 所以我们可以直接计算被涂为黑色的格数
因为给定了涂色的左下和右上位置 我们可以用上面的方法求出这个矩形的黑格个数b和白格个数w
此时将这个矩形涂为黑色 对 W 和 B 的影响 就是 B+=w , W-=w ; ( 即把白格涂为黑色就够了 )
(那么将一个矩形涂为白色也同理 B+=b , W-=b ; )
而白色可能会被黑色覆盖 就是说白色的部分会被黑色所切割
那么我们只要把多出的部分割出来涂为白色就可以了 我们来画个图
骗人的~ 不放图了 看代码把很好懂
#include
#define LL long long
using namespace std;
LL n,m,B,W;
LL X1,Y1,X2,Y2,X3,Y3,X4,Y4;
void col(LL lx,LL ly,LL rx,LL ry,bool flag) {
LL N=ry-ly+1LL, M=rx-lx+1LL, b, w;
if((lx+ly)%2LL) // 最左下一格为黑色
w=N\*M/2LL, b=w+(N\*M%2LL);
else // 否则为白色
b=N\*M/2LL, w=b+(N\*M%2LL);
if(flag) W+=b, B-=b; // 涂白
else B+=w, W-=w; // 涂黑
}
void cut(LL lx,LL ly,LL rx,LL ry) {
if(lx>rx || ly>ry) return; // 矩形不合法
if(rx
col(lx,ly,rx,ry,); return;
} // 当前矩形不会被黑色部分切割到 直接涂为白色
if(lx
if(ly
}
int main()
{
int t; scanf("%d",&t);
while(t--) {
scanf("%I64d%I64d",&n,&m);
B=n*m/2LL, W=B+(n*m%2LL);
scanf("%I64d%I64d%I64d%I64d",&X1,&Y1,&X2,&Y2);
scanf("%I64d%I64d%I64d%I64d",&X3,&Y3,&X4,&Y4);
cut(X1,Y1,X2,Y2);
col(X3,Y3,X4,Y4,);
printf("%I64d %I64d\n",W,B);
}
return ;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章