CCF CSP 202303-1 田地丈量

首先理解题意，题目意思很明确，就是找到重叠矩形的面积和，第一想法是想使用一个标志数组对每一个矩形所覆盖的地方进行标志，最后遍历选择的矩形面，对已经标志过的点计数即可，但是由于这里输入坐标的最大值可以达到10^4，而我们遍历矩形需要嵌套for循环就可能导致超时，这个想法就放弃了

思路二，仔细观察我们其实不难发现我们只需将矩形与原矩形没有交集的地方切掉，那么矩形的面积就是重叠的面积了，但是这里我们需要先将不可能有交集的情况列出来并且排除，这里也不难得到，就是当矩形的左边界大于等于原矩形的右边界、矩形的上边界小于等于原矩形的下边界、矩形的右边界小于等于原矩形的左边界、矩形的下边界大于等于原矩形的上边界（这里的原矩形即（0，0）与（a，b）形成的矩形），将这四种情况排除，剩下的情况就都是有交集的情况了，再将没有交集的地方切割即可

#include<iostream>

using namespace std;

int ans=0;
int n,a,b;

int main(){
	cin>>n>>a>>b;
	for(int i=0;i<n;i++){
		int x1,y1,x2,y2;
		cin>>x1>>y1>>x2>>y2;
		if(y2<=0||y1>=b||x1>=a||x2<=0){//不可能有交集的四种情况 
			continue;
		}		
		//剩下有交集的情况 
		if(x1<0){//将没有交集的地方切割掉 
			x1=0;
		}
		if(x2>a){
			x2=a;
		}
		if(y1<0){
			y1=0;
		}
		if(y2>b){
			y2=b;
		}
		ans+=((x2-x1)*(y2-y1));
	}
	cout<<ans<<endl;
	return 0;
}

思路三：

交叉部分面积（以两个矩形为例），交叉部分矩阵右边界即原两个大矩阵的右边界中的较小值，左边界即原两个大矩阵的左边界中的较大值。因此，交叉矩阵的宽即为右边界减去左边界x = min(a, x2) - max(0, x1);同理可得上边界和下边界的关系 y = min(b, y2) - max(0, y1);最后，通过判断x 和 y是否大于零，从而判断两个矩阵之间是否存在交叉部分，若存在则 sum += x * y; 如果两个矩形完全没有交集则必然x或y存在一个或多个<=0

#include <iostream>

using namespace std;

int main()
{
    int n, a, b;
    int x1, y1, x2, y2;
    int x, y;
    int sum = 0;
    cin >> n >> a >> b;
    for(int i = 1; i <= n; i++){
        cin >> x1 >> y1 >> x2 >> y2;
        x = min(a, x2) - max(0, x1);
        y = min(b, y2) - max(0, y1);
        if(x >= 0 && y >= 0)
            sum += x * y;
    }
    cout << sum;
    return 0;
}
 

参考自