P1884 [USACO12FEB] Overplanting S

题目描述

Farmer John has purchased a new machine that is capable of planting grass within any rectangular region of his farm that is “axially aligned” (i.e., with vertical and horizontal sides). Unfortunately, the machine malfunctions one day and plants grass in not one, but N (1 <= N <= 1000) different rectangular regions, some of which may even overlap.

Given the rectangular regions planted with grass, please help FJ compute the total area in his farm that is now covered with grass.

在一个笛卡尔平面坐标系里（则 $X$ 轴向右是正方向，$Y$ 轴向上是正方向），有 $N\ (1 \le N \le 1000)$ 个矩形，第 $i$ 个矩形的左上角坐标是 $(x_1,y_1)$，右下角坐标是 $(x_2,y_2)$。问这 $N$ 个矩形所覆盖的面积是多少？

注意：被重复覆盖的区域的面积只算一次。

输入格式

第一行，一个整数 $N\ (1 \le N \le 1000)$。

接下来有 $N$ 行，每行描述一个矩形的信息，分别是矩形的 $x_1,y_1,x_2,y_2(-10^8 \le x_1,y_1,x_2,y_2 \le 10^8)$。

输出格式

一个整数，被 $N$ 个矩形覆盖的区域的面积。

输入输出样例 #1

输入 #1

1
2
3
2
0 5 4 1
2 4 6 2

输出 #1

1
20

题解

  • 本题涉及空间较大 需对二维空间进行离散
  • 此处选用统一离散 即将所有x和y坐标放进一个数组里排序去重 再映射为新的下标
  • 在映射后的图f中使用差分标记覆盖 注意此处f[i][j] 表示的是一个没有面积的点 而c[i+1]-c[i] 表示该点右下角小矩形的宽 所以在标记f的过程中要记住标记的是每个小矩形的左上角
  • 另外需要注意的是本题使用的是笛卡尔坐标系 与通常行列表示有所不同 左上角与右下角也是在笛卡尔坐标系中而言 需要转换

代码与注释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;
#define MAXN 4010
int n, btop, ctop;
int a[MAXN][4];
int b[MAXN], c[MAXN];
int f[MAXN][MAXN];
map<int, int> Map;
int main() {
    scanf("%d", &n);
    for(int i=1; i<=n; i++) {
        for(int j=0; j<4; j++) {
            scanf("%d", &a[i][j]);
            b[++btop] = a[i][j];
        }
    }
    // 对二维空间进行统一离散化
    sort(b+1, b+btop+1);
    for(int i=1; i<=btop; i++) {
        if(i==1 || b[i]!=b[i-1]) {
            c[++ctop] = b[i];
            Map[b[i]] = ctop;
        }
    }
    for(int i=1; i<=n; i++) {
        int x = Map[a[i][0]], y = Map[a[i][1]];
        int xx = Map[a[i][2]], yy = Map[a[i][3]];
        f[x][yy]++;
        f[x][y]--;
        f[xx][yy]--;
        f[xx][y]++; // 注意这里差分标记的时候不标(xx, yy) 因为这里标记的相当于每个小矩形的左上角
    }
    // a[i][j] = a[i-1][j]+a[i][j-1]-a[i-1][j-1] + b[i][j]
    long long ans = 0;
    for(int i=1; i<=ctop-1; i++) {
        for(int j=1; j<=ctop-1; j++) { // 注意边界 之后有i+1,j+1 此处右边界应设置为ctop-1
            f[i][j] = f[i-1][j]+f[i][j-1]-f[i-1][j-1]+f[i][j];
            // cout << f[i][j] << " ";
            if(f[i][j] > 0) {
                // cout << c[i+1] << c[i] << c[j+1] << c[j] << endl;
                ans += (long long)(c[i+1]-c[i]) * (c[j+1]-c[j]);
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}