题目描述

给定一个边界矩形区域 (0, 0) 到 (a, b) 和多个矩形田地的位置，每个田地用 (x1, y1, x2, y2) 表示，表示该田地的左下角坐标为 (x1, y1)，右上角坐标为 (x2, y2)。要求计算所有田地与边界矩形的重叠面积之和。

输入

• 第一行包含三个整数：n 表示田地的数量，a 和 b 表示边界矩形的右上角坐标。
• 接下来的 n 行，每行包含四个整数 x1, y1, x2, y2，表示每个田地的左下角和右上角坐标。

输出

输出一个整数，表示所有田地与边界矩形的重叠面积的总和。

样例

4 10 10
0 0 5 5
5 -2 15 3
8 8 15 15
-2 10 3 15

输出

44

算法1

我们通过暴力枚举每个田地与边界矩形的重叠面积来求解。具体思路如下：

1. 对于每个田地，先通过 max 和 min 操作计算与边界矩形重叠的区域的坐标。
2. 如果重叠区域有效，即左下角坐标小于右上角坐标，那么计算这个重叠区域的面积。
3. 将所有有效的重叠面积累加得到总面积。

步骤：

1. 对每个田地的坐标 (x1, y1, x2, y2)，计算其与边界矩形 (0, 0, a, b) 的重叠区域。
2. overlap_x1 = max(0, x1)：重叠区域的左边界。
3. overlap_y1 = max(0, y1)：重叠区域的下边界。
4. overlap_x2 = min(a, x2)：重叠区域的右边界。

5. overlap_y2 = min(b, y2)：重叠区域的上边界。

6. 判断计算出的重叠区域是否有效，即：

7. overlap_x1 < overlap_x2 且 overlap_y1 < overlap_y2，只有这样才能构成有效的矩形区域。

8. 计算重叠面积并累加。

时间复杂度

由于我们只对每个田地的坐标进行一次简单的计算，整个过程的时间复杂度为 $O(n)$，其中 $n$ 是田地的数量。

Python 代码

# 输入田地数和边界矩形的右上角坐标
n, a, b = map(int, input().split())

# 读取所有田地的坐标
locations = [list(map(int, input().split())) for _ in range(n)]

# 初始化总面积
area = 0

# 遍历每个田地
for land in locations:
    x1, y1, x2, y2 = land

    # 计算与边界矩形的重叠部分
    overlap_x1 = max(0, x1)
    overlap_y1 = max(0, y1)
    overlap_x2 = min(a, x2)
    overlap_y2 = min(b, y2)

    # 判断重叠区域是否有效
    if overlap_x1 < overlap_x2 and overlap_y1 < overlap_y2:
        # 计算重叠面积并累加
        area += (overlap_x2 - overlap_x1) * (overlap_y2 - overlap_y1)

# 输出总面积
print(area)

参考文献

无