第十三届蓝桥杯省赛（2022年4月17日）C++中级组题解

        小蓝要给墙面上的n个矩形区域粉刷涂料, 给出每个矩形左下角和右上角的两个坐标(x1,y1, x2,y2). 请帮助小蓝计算下粉刷涂料的面积是多少, 如果矩形之间有重叠部分只计算一次.

        例如: 有2个矩形，2个矩形左下角和右上角的两个坐标分别为: (2,2,9,5)、(6,1,12,9),

其粉刷涂料的面积是60.

        输入描述：

        先输入n的值；
        再输入分为n行, 每行有四个正整数x1,y1, x2,y2 (1

        输出描述：

        输出一个整数，表示粉刷涂料的面积是多少.

        样例输入：

        2

        2 2 9 5

        6 1 12 9

        样例输出：

        60

        法一：由于N是不确定的，也就是矩形的数量不确定，在矩形较多的情况下，互相覆盖的情况复杂，不容易用坐标值相减来进行计算。

        于是我们把每个矩形看作是一个点阵。比如一个3x3的矩形，可以看作有3行3列共9个点组成的二维数组。

        把整个坐标系，看作是一个大的二维数组，xy[0][0]即是坐标系的原点，行号代表x轴的值，列号看成y轴得值，那么每个矩形就是这个二维数组中的一部分。

        因此每输入一个矩形的坐标，就可以根据坐标位置在二维数组中取对应得部分，为这些部分得每个数组元素中赋值为True，代表有面积.

        最终数组中值为False得，说明没有矩形能覆盖到，值为True得说明只有一个矩形覆盖到了。

        最终遍历整个点阵数组中的每个元素，累计有数字的元素个数，即最后的面积。

        法二：二维前缀和容斥原理:

         左上角(a,b),右下角(c,d)的矩形区域总和为: 

        s[c][d]-s[c][b]-s[a][d]+s[a][b]

        把上述过程反过来, 就得到了到二维差分(本题中, 权 c=1):

        m[a][b]+=c;

        m[c][b]-=c;

        m[a][d]-=c;

        m[c][d]+=c;

#include//调用输入输出流头文件
using namespace std;//使用标准名字空间
bool xy[110][110];//二维数组，用来组成点阵信息
int ans;//定义整数类型变量ans
int main(){//主函数开始
	int n;//定义整数类型变量
	cin>>n;//输入n的值
	int x1,y1,x2,y2;//定义整数类型变量x1,x2,y1,y2
	for(int i=0;i>x1>>y1>>x2>>y2;//循环输入每一个矩形的坐标信息
		for(int j=y1+1;j<=y2;j++)  
			for(int k=x1+1;k<=x2;k++)
				xy[j][k]=1;//记录每个矩形点阵信息
	}	
	for(int j=1;j<=109;j++){//for循环，计数器i从1自增到109，共循环109次
		for(int k=1;k<=109;k++)//for循环，计数器k从1自增到109，共循环109次
			if(xy[j][k]) ans++;//累积数组中为真的个数，即为面积 
	}
	cout<

#include//调用输入输出流头文件
using namespace std;//使用标准名字空间
int a[509][509],n;
int main(){//主函数开始
	int x1,y1,x2,y2;//定义整数类型x1,x2,y1,y2
    cin>>n;//输入n的值
    for(int i=0;i>x1>>y1>>x2>>y2;//输入x1,y1,x2,y2
        a[x1+1][y1+1]++;//a[x1+1][y1+1]自增1
        a[x2+1][y1+1]--;//a[x2+1][y1+1]自减1
        a[x1+1][y2+1]--;//a[x1+1][y2+1]自减1
        a[x2+1][y2+1]++;//a[x2+1][y2+1]自增1
    }
	long long sum=0;//定义长整数类型变量sum并初始化赋值为0
	for(int i=1;i<=20;++i)//for循环，计数器i从1自增到20，共循环20次
		for(int j=1;j<=20;++j){//for循环，计数器j从1自增到20，共循环20次
			a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];//a[i][j]自增a[i-1][j]+a[i][j-1]-a[i-1][j-1]
			//此时 a[i][j]里记录的就是每个点被覆盖的次数 
			if(a[i][j]>0) sum++;//如果a[i][j]>0,sum自增1
		}		
	cout<