05_Rectangle Geometry 矩形几何

Rectangle Geometry 矩形几何

什么是矩形几何问题？

矩形几何问题是指涉及边平行于坐标轴的矩形的计算问题。这类问题在 USACO Bronze 中非常常见，主要考察对矩形面积、交集等概念的理解。

矩形表示方法

通常使用两个对角顶点来表示矩形： - 左下角 (bottom-left)：(bl_x, bl_y) - 右上角 (top-right)：(tr_x, tr_y)

注意：bl_x < tr_x 且 bl_y < tr_y

---

常用公式

1. 矩形面积

面积 = (tr_x − bl_x) × (tr_y − bl_y)

def area(bl_x, bl_y, tr_x, tr_y):
    return (tr_x - bl_x) * (tr_y - bl_y)

2. 判断两矩形是否相交

两个矩形不相交的条件是：其中一个矩形完全在另一个的左侧、右侧、上方或下方。

矩形 s1 和 s2 相交的充要条件： - s1 的左边界在 s2 的右边：不存在 - s1 的右边界在 s2 的左边：不存在 - s1 的下边界在 s2 的上边：不存在 - s1 的上边界在 s2 的下边：不存在

即：相交 = NOT (分离的任意条件)

def intersect(s1, s2):
    # s = (bl_x, bl_y, tr_x, tr_y)
    # 不相交的情况：s1 在 s2 的左边/右边/上边/下边
    if s1[2] <= s2[0] or s2[2] <= s1[0]:  # 左右分离
        return False
    if s1[3] <= s2[1] or s2[3] <= s1[1]:  # 上下分离
        return False
    return True

3. 求两矩形交集面积

如果两矩形相交，交集矩形的边界： - 左边界 = max(s1.bl_x, s2.bl_x) - 右边界 = min(s1.tr_x, s2.tr_x) - 下边界 = max(s1.bl_y, s2.bl_y) - 上边界 = min(s1.tr_y, s2.tr_y)

交集面积 = (min(tr_x) − max(bl_x)) × (min(tr_y) − max(bl_y))

def inter_area(s1, s2):
    # 计算交集矩形的边界
    left = max(s1[0], s2[0])
    right = min(s1[2], s2[2])
    bottom = max(s1[1], s2[1])
    top = min(s1[3], s2[3])

    # 如果没有交集，返回 0
    if left >= right or bottom >= top:
        return 0

    return (right - left) * (top - bottom)

---

经典例题：Fence Painting（油漆围栏）

题目描述

https://usaco.org/index.php?viewproblem2&cpid=590

农民 John 有一个矩形牛棚墙壁，需要重新油漆。给出 N 个已油漆过的矩形区域，现在要油漆一个新的矩形区域。求新油漆的面积（不重复计算已有油漆的区域）。

算法思路

核心问题：求新矩形与已有矩形交集面积的总和。

快速解法：O(1)

使用区间交集公式：新面积 = 新矩形面积 - 与已有矩形的交集面积之和。

def inter_len(a1, a2, b1, b2):
    """一维区间交集长度"""
    left = max(a1, b1)
    right = min(a2, b2)
    return max(0, right - left)

# 读取输入
N = int(input())
rects = [tuple(map(int, input().split())) for _ in range(N)]
new_rect = tuple(map(int, input().split()))

# 新矩形面积
new_area = (new_rect[2] - new_rect[0]) * (new_rect[3] - new_rect[1])

# 计算与已有矩形的交集面积总和
total_inter = 0
for rect in rects:
    inter_x = inter_len(rect[0], rect[2], new_rect[0], new_rect[2])
    inter_y = inter_len(rect[1], rect[3], new_rect[1], new_rect[3])
    total_inter += inter_x * inter_y

# 最终答案
ans = new_area - total_inter
print(ans)

时间复杂度

• 慢速解法：O(max_coordinate²)，空间 O(max_coordinate²)
• 快速解法：O(N)，空间 O(1)

---

经典例题：Blocked Billboard（被遮挡的广告牌）

题目描述

https://usaco.org/index.php?viewproblem2&cpid=764

有两个矩形广告牌，其中一个被卡车遮挡。求未被遮挡的可见部分面积。

算法思路

核心问题：求第一个矩形未被第二个矩形遮挡的面积。

可视作：第一个矩形面积 - 与第二个矩形的交集面积

慢速解法：O((max coordinate)²)

MAX = 1000

# 创建网格
grid = [[0] * MAX for _ in range(MAX)]

# 标记第一个矩形（广告牌1）
billboard = list(map(int, input().split()))
for x in range(billboard[0], billboard[2]):
    for y in range(billboard[1], billboard[3]):
        grid[x][y] = 1

# 标记第二个矩形（卡车）
truck = list(map(int, input().split()))
for x in range(truck[0], truck[2]):
    for y in range(truck[1], truck[3]):
        grid[x][y] = 0  # 被遮挡

# 统计可见部分
ans = sum(grid[x][y]
          for x in range(billboard[0], billboard[2])
          for y in range(billboard[1], billboard[3]))

print(ans)

快速解法：O(1)

二维类比一维区间交集公式。

def rect_area(rect):
    """矩形面积"""
    return (rect[2] - rect[0]) * (rect[3] - rect[1])

def inter_area(r1, r2):
    """两矩形交集面积"""
    left = max(r1[0], r2[0])
    right = min(r1[2], r2[2])
    bottom = max(r1[1], r2[1])
    top = min(r1[3], r2[3])

    if left >= right or bottom >= top:
        return 0
    return (right - left) * (top - bottom)

# 读取输入
billboard = tuple(map(int, input().split()))
truck = tuple(map(int, input().split()))

# 可见面积 = 广告牌面积 - 交集面积
visible = rect_area(billboard) - inter_area(billboard, truck)
print(visible)

时间复杂度

• 慢速解法：O(max_coordinate²)
• 快速解法：O(1)

---

核心要点

1. 矩形表示：使用左下角和右上角坐标 (bl_x, bl_y, tr_x, tr_y)
2. 判断相交：检查是否存在分离条件（左右分离或上下分离）
3. 交集面积：对 x 和 y 分别求交集区间长度，然后相乘
4. 一维到二维：先理解一维区间交集，再类比到二维矩形
5. 快速解法：对于坐标范围大的情况，必须使用 O(1) 公式解法