CF1080C Masha and two friends_综合

题目：Masha and two friends

思路：

首先这题思路很简单，模拟+容斥就可以了。

即最终的白块数 = 原网格图的白块数 + 涂白增加的白块数 - 涂黑减少的白块数 - 又涂了白又涂了黑的那一块减少的白块数。

这里重点说下怎么求两矩形交，我最开始就是这里不会写的。

下面的题解大多分类讨论了，其实可以不用讨论的。

如图，要求黑色矩形和红色居心的交。

在这里插入图片描述

设黑色矩形左上角坐标 ( x1 , y1 )，右下角 ( x2 , y2 ) ;

红矩形左上角坐标 ( a1 , b1 )，右下角 ( a2 , b2 )。

根据重点公式，可以算出 $\frac{ x1 + x2 }{2} , \frac{ y1 + y2 }{2} ) ，O2 = ( \frac{ a1 + a2 }{2} , \frac{ b1 + b2 }{2})$ 。

所以相交的条件就是：

$abs(\frac{ x1 + x2 }{2}-\frac{ a1 + a2 }{2})<=\frac{x2-x1}{2}+\frac{a2-a1}{2}$

且

$abs(\frac{ y1 + y2 }{2}-\frac{ b1 + b2 }{2})<=\frac{y2-y1}{2}+\frac{b2-b1}{2}$

整理得

$a b s (x 1 + x 2 ? a 1 ? a 2) < = x 2 ? x 1 + a 2 ? a 1$

且

$a b s (y 1 + y 2 ? b 1 ? b 2) < = y 2 ? y 1 + b 2 ? b 1$

判断完相交，就是求相交部分的坐标了。

也很好看出来，左上角是 $(m a x (x 1, a 1), m i n (x 2, a 2))$ ，右下角是 $(m a x (y 1, b 1), m i n (y 2, b 2))$ 。

代码：

#include<bits/stdc++.h>
using namespace std;#define read(x) scanf("%d",&x)
#define ll long longll gets(int x,int y) {
    return ((ll)x*y+1)/2;
}ll find(int x1,int y1,int x2,int y2) {
    x1--,y1--;return gets(x2,y2)+gets(x1,y1)-gets(x1,y2)-gets(x2,y1);
}int n,m;int main() {
    int T;read(T);while(T--) {
    read(n),read(m);int x1,y1,x2,y2;read(x1),read(y1),read(x2),read(y2);int a1,b1,a2,b2;read(a1),read(b1),read(a2),read(b2);ll ans=find(1,1,n,m);ans+=((ll)x2-x1+1)*(y2-y1+1)-find(x1,y1,x2,y2);ans-=find(a1,b1,a2,b2);if(abs(x1+x2-a1-a2)<=(x2-x1+a2-a1)&&abs(y1+y2-b1-b2)<=(y2-y1+b2-b1)) {
    ans-=((ll)min(x2,a2)-max(x1,a1)+1)*(min(y2,b2)-max(y1,b1)+1)-find(max(x1,a1),max(y1,b1),min(x2,a2),min(y2,b2));}printf("%I64d %I64d\n",ans,((ll)n*m)-ans);}return 0; 
}