ABC449D-Make-Target-2

题目大意

给定矩形区域，点 $(x,y)$ 颜色由 $k=\max(|x|，|y|)$ 决定：$k$ 为偶数时为黑，为奇数时白。求区域内黑色点数。

思路

颜色由 $k=\max(|x|,|y|)$ 的奇偶性决定，$k$ 为偶数时点是黑色。我们将图形看作一层层套在一起的正方形环，第 $i$ 环就是边长范围从 $-i$ 到 $i$ 的大正方形区域，扣除掉内部从 $-(i-1)$ 到 $i-1$ 的小正方形区域后剩下的部分。

设 $S_i$ 为大正方形与目标矩形的重叠格子数，只需算出横竖两个方向重叠长度的乘积即可。那么第 $i$ 环在矩形内的实际格子数，就等于 $S_i$ 减去 $S_{i-1}$，这样就把复杂的环形计算变成了简单的减法。

最后从 $0$ 开始枚举每一层，如果层数 $i$ 是偶数，就将算出的差值加入答案；如果是奇数则跳过。这种方法避免了复杂的几何分类，只需循环计算并累加，就能快速得出黑色格子的总数。

Code

#include<bits/stdc++.h>
using namespace std;
long long l,r,u,d,ans,p;
int main(){
	cin>>l>>r>>d>>u;
	long long t=max({abs(l),abs(r),abs(u),abs(d)});
	for(long long i=0;i<=t;i++){
		int lm=max(l,-i);
		int rm=min(r, i);
		int dm=max(d,-i);
		int um=min(u, i);
		long long n;
		if(lm<=rm&&dm<=um){
			n=1ll*(rm-lm+1)*(um-dm+1);
		}else n=0;
		if(i&1)ans+=n-p;
		p=n;
	}
	cout<<ans;
}