题目描述

　　​有N个矩形，每个矩形给出左上角的坐标和右下角的坐标。

　　这些矩形有可能有重叠的部分。求这N个矩形的覆盖的面积总和，重叠部分只算一次面积。

 

输入输出格式

输入格式

　　第1行:  一个整数 N， 1 <= N <= 10。

　　接下来有N行，每行4个整数：   x1  y1 x2 y2， 其中（x1,y1）是左上角， (x2,y2)是右下角.  坐标范围是【 -10000 ，10000】

 

输出格式

　　N个矩形总共覆盖的面积总和。

 

 

输入输出样例

输入样例

2

0 5 4 1

2 4 6 2

 

输出样例

20

 

题解

　　容斥原理裸题，具体如下。

#include 
      
       #define MAX_N (10 + 5)using namespace std;int n;long long x1[MAX_N], y1[MAX_N], x2[MAX_N], y2[MAX_N];long long ans;void DFS(long long lx, long long rx, long long ly, long long ry, int dep, int now){    if(lx >= rx || ly >= ry) return;    if(dep & 1) ans += (rx - lx) * (ry - ly);    else ans -= (rx - lx) * (ry - ly);    for(register int i = now; i <= n; ++i)    {        DFS(max(lx, x1[i]), min(rx, x2[i]), max(ly, y1[i]), min(ry, y2[i]), dep + 1, i + 1);    }    return;}int main(){    cin >> n;    for(register int i = 1; i <= n; ++i)    {        cin >> x1[i] >> y2[i] >> x2[i] >> y1[i];    }     for(register int i = 1; i <= n; ++i)    {        DFS(x1[i], x2[i], y1[i], y2[i], 1, i + 1);    }    cout << ans;    return 0;}