过度种植

农夫约翰购买了一台新机器，该机器能够在其农场的任何“轴向对齐”（即具有垂直和水平边）的矩形区域内种草。

不幸的是，这台机器有一天出了故障，并在 $N$ 个不同的矩形区域内进行了种草工作，其中一些区域可能会有重叠。

给定机器工作的具体 $N$ 个矩形区域，请你计算种上草的区域的总面积是多少。

输入格式

第一行包含整数 $N$。

接下来 $N$ 行，每行包含四个整数 $x_{1},y_{1},x_{2},y_{2}$，表示其中一个矩形区域的左上角坐标 $\left( {x_{1},y_{1}} \right)$ 和右下角坐标 $\left( {x_{2},y_{2}} \right)$。

输出格式

输出种上草的区域的总面积。

数据范围

$1\ leq N \leq 10$,
$?10000 \leq x_{1},y_{1},x_{2},y_{2} \leq 10000$,
$x_{1} < x_{2}$，
$y_{1} > y_{2}$。

输入样例：

2
0 5 4 1
2 4 6 2

输出样例：

20

解题思路

　　如果$N$比较大的话，例如$N = 1000$，就需要用到扫描线。如果$N = 10000$还需要用到线段树来优化。但这里的$N$最大为$10$，并不需要用到那么复杂的写法。容易发现这些矩形的并集是一个不规则的图形，比较难求，但这些矩形的交集也是矩形，就比较好求了。因此我们发现并集不好求而交集好求，就可以用到容斥原理。容斥原理的公式如下：$$\left| \bigcup\limits_{1 \leq i \leq n} {S_{i}} \right| = \sum\limits_{1 \leq i \leq n} {\left| S_{i} \right|} -  \sum\limits_{1 \leq {i

　　这样就可以把求并集的问题转换为求交集的问题。虽然交集好求，但项数很多，一共有$C_{n}^{1} + C_{n}^{2} + \dots + C_{n}^{n} = 2^{n} - 1$项，由于$N$最大只有$10$，因此最多也就只有$1023$项，再加上求所有矩形的交集，因此时间复杂度为$O \left( 2^{n} \times n \right)$。

　　矩形求交集其实就是区间求交，我们把$X$轴和$Y$轴独立开来看，例如$X$轴上有两个区间$\left[ {a,b} \right]$和$\left[ {c,d} \right]$，那么这两个区间的交集就是$\left[ {max \{{a,c}\},~ min \{{b,d}\}} \right]$。同理$Y$轴的区间求交也是如此。

　　我们在枚举每次求交集的矩形个数的时候（也就是枚举$C_{n}^{i}$），可以用二进制枚举。同时读入的坐标是数学坐标系，$y_{1} > y_{2}$，为了让$y_{1} < y_{2}$与$x_{1} < x_{2}$保持一致方便区间求交，我们把坐标系变成矩阵坐标系，即把左上角的点和右下角的点转化成左下角的点和右上角的点。

　　AC代码如下：

 1 #include 
 2 using namespace std;
 3 
 4 const int N = 15, INF = 0x3f3f3f3f;
 5 
 6 int n;
 7 struct Node {
 8     int x1, y1, x2, y2;
 9 }p[N];
10 
11 int get(int st) {
12     // 初始定义一个无穷大的矩形
13     int x1 = -INF, y1 = -INF, x2 = INF, y2 = INF, cnt = 0;
14     for (int i = 0; i < n; i++) {
15         if (st >> i & 1) {
16             cnt++;  // 求交矩阵个数+1
17             
18             // x轴上求交
19             x1 = max(x1, p[i].x1);
20             x2 = min(x2, p[i].x2);
21             
22             // y轴上求交
23             y1 = max(y1, p[i].y1);
24             y2 = min(y2, p[i].y2);
25         }
26     }
27     
28     int ret = max(x2 - x1, 0) * max(y2 - y1, 0);    // 有可能没有交集，算出是负数，因此要与0取最大值
29     if (cnt % 2 == 0) ret *= -1;    // 如果矩形的个数为偶数，根据公式要返回负数值
30     
31     return ret;
32 }
33 
34 int main() {
35     scanf("%d", &n);
36     for (int i = 0; i < n; i++) {
37         scanf("%d %d %d %d", &p[i].x1, &p[i].y2, &p[i].x2, &p[i].y1);   // y1 < y2
38     }
39     
40     int ret = 0;
41     for (int i = 1; i < 1 << n; i++) {
42         ret += get(i);  // 获取i状态下（i的二进制有多少个1）的矩形求交的面积
43     }
44     printf("%d", ret);
45     
46     return 0;
47 }

参考资料

　　AcWing 2032. 过度种植（春季每日一题2022）：https://www.acwing.com/video/3878/