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) \times (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)) \times (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?page=viewproblem2&cpid=567

农民 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(N)，空间 O(1)

---

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

题目描述

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

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

算法思路

核心问题：求两个广告牌各自未被卡车遮挡的面积之和。

可视作：两个广告牌面积之和 - 各自与卡车交集面积之和

快速解法：O(1)

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

import sys
sys.stdin = open("billboard.in", "r")
sys.stdout = open("billboard.out", "w")

def count_s(x1, y1, x2, y2):
    s = (y2 - y1) * (x2 - x1)
    return s

def inter_area(n1, n2):
    left = max(n1[0], n2[0])
    bottom = max(n1[1], n2[1])
    right = min(n1[2], n2[2])
    top = min(n1[3], n2[3])

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

board1 = tuple(map(int, input().split()))
board2 = tuple(map(int, input().split()))
truck = tuple(map(int, input().split()))

s1 = count_s(board1[0], board1[1], board1[2], board1[3])
s2 = count_s(board2[0], board2[1], board2[2], board2[3])

sum_of_s = s1 + s2

intersetion = inter_area(board1, truck) + inter_area(board2, truck)

ans = sum_of_s - intersetion

print(ans)

时间复杂度

• 快速解法：O(1)

---

经典例题：Billboard（广告牌）

题目描述

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

有两个广告牌：

• 割草机广告牌（Lawnmower）：(x1, y1) 到 (x2, y2)
• 牛饲料广告牌（Cow Feed）：(x3, y3) 到 (x4, y4)

饲料广告牌可能会部分或完全遮挡割草机广告牌。求覆盖剩余可见部分所需的最小矩形帆布面积。

算法思路

核心问题：判断饲料广告牌遮挡了割草机广告牌的哪些部分。

关键观察：

1. 完全遮挡：如果饲料广告牌覆盖了对角两个角（左下+右上或右上+左下），则完全遮挡 → 面积 0
2. 部分遮挡：如果饲料广告牌覆盖了两个相邻的角，则剩余可见部分是一个矩形，可以用一块帆布覆盖
3. 其他情况：需要完整的割草机广告牌面积

快速解法：O(1)

import sys
sys.stdin = open("billboard.in", "r")
sys.stdout = open("billboard.out", "w")

x1, y1, x2, y2 = map(int, input().split())
x3, y3, x4, y4 = map(int, input().split())

tl = y4 >= y2 and x3 <= x1
tr = y4 >= y2 and x4 >= x2
br = x4 >= x2 and y4 <= y1
bl = x3 <= x1 and y3 <= y1

if bl and tr:
    print(0)
    exit()

left = max(x1, x3)
bottom = max(y1, y3)
right = min(x2, x4)
top = min(y2, y4)

s1 = (x2 - x1) * (y2 - y1)
inter = (right - left) * (top - bottom)

if tl + tr + br + bl == 2:
    print(s1 - inter)

else:
    print(s1)

时间复杂度

• 快速解法：O(1)

---

核心要点

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