这一类的大多数问题只包含两三个正方形或矩形，此时可以直接在纸上画出各种情况， 通常就能顺理成章地得到解法。

示例——Fence Painting

较慢的解法

由于所有区间都位于 $[0,100]$ 范围内，可以用循环把每个给定区间中所有长度为 $1$ 的小区间标记为已涂色。答案就是被标记的小区间数量。

时间复杂度： $\mathcal{O}(\text{最大坐标})$

Copy
import sys

MAX_POS = 100

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

a, b = map(int, input().split())
c, d = map(int, input().split())

不过，当限制更大时（例如坐标达到 $10^9$），这种解法将不可行。

较快的解法

把两个原区间的长度相加，再减去交集长度，即可算出答案。

官方题解把交集 长度的计算分成了多种情况，但可以采用更简单的方法。当 $a\le x$、$c\le x$、 $x<b$ 且 $x<d$ 时，区间 $[x,x+1]$ 同时包含在 $[a,b]$ 和 $[c,d]$ 中；换言之， 需要满足 $\max(a,c)\le x$ 且 $x<\min(b,d)$。因此，如果 $\min(b,d)-\max(a,c)$ 为正数，交集长度就是这个值，否则为零！

时间复杂度： $\mathcal{O}(1)$

Copy
import sys

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

a, b = map(int, input().split())
c, d = map(int, input().split())
total = (b - a) + (d - c)  # the sum of the two intervals
intersection = max(min(b, d) - max(a, c), 0)  # subtract the intersection
union = total - intersection

print(union)

示例——Blocked Billboard

可以把本题看作上一个示例的二维版本。

较慢的解法

时间复杂度： $\mathcal{O}((\text{最大坐标})^2)$

由于所有坐标都在 $[-1000,1000]$ 范围内，可以使用嵌套 for 循环遍历全部 $2000^2$ 个可能可见的单位正方形，并检查哪些确实可见。

Copy
import sys

MAX_POS = 2000


def main():
	sys.stdin = open("billboard.in", "r")
	sys.stdout = open("billboard.out", "w")

	visible = [[False for _ in range(MAX_POS)] for _ in range(MAX_POS)]

如果坐标上限改为 $10^9$，这种方法就不够用了。

较快的解法

时间复杂度： $\mathcal{O}(1)$

官方题解

Copy
import sys


class Rect:
	def __init__(self):
		# Read rectangle coordinates from input
		self.x1, self.y1, self.x2, self.y2 = map(int, input().split())

	def area(self):
		# Calculate area of the rectangle

常用公式

矩形几何问题中经常出现一些特定任务。例如，许多问题要求根据坐标点求两个或多个 矩形的重叠面积，或判断两个矩形是否相交。下面讨论这些公式。

注意，这些公式仅适用于边与坐标轴平行的矩形。

计算面积

单个矩形的面积公式为 $w\cdot l$。

$\texttt{length}$ 是竖直边的长度，$\texttt{width}$ 是水平边的长度。

1. $\texttt{width} = \texttt{tr}_x - \texttt{bl}_x$
2. $\texttt{length} = \texttt{tr}_y - \texttt{bl}_y$
3. $\texttt{area} = \texttt{width} \cdot \texttt{length}$

实现

Copy
def area(bl_x: int, bl_y: int, tr_x: int, tr_y: int) -> int:
	length = tr_y - bl_y
	width = tr_x - bl_x
	return length * width

检查两个矩形是否相交

给定两个矩形 $a$ 和 $b$，它们不相交的情况只有两种：

1. $\texttt{tr}_{a_y}$ $\leq$ $\texttt{bl}_{b_y}$ or $\texttt{bl}_{a_y}$ $\geq$ $\texttt{tr}_{b_y}$.
2. $\texttt{bl}_{a_x}$ $\geq$ $\texttt{tr}_{b_x}$ or $\texttt{tr}_{a_x}$ $\leq$ $\texttt{bl}_{b_x}$.

其他所有情况下，两个矩形都相交。

实现

Copy
def intersect(s1, s2) -> bool:
	bl_a_x, bl_a_y, tr_a_x, tr_a_y = s1[0], s1[1], s1[2], s1[3]
	bl_b_x, bl_b_y, tr_b_x, tr_b_y = s2[0], s2[1], s2[2], s2[3]

	# no overlap
	if bl_a_x >= tr_b_x or tr_a_x <= bl_b_x or bl_a_y >= tr_b_y or tr_a_y <= bl_b_y:
		return False
	else:
		return True

计算交集面积

假定两个矩形的交集所形成的形状本身也是矩形。

首先求出这个矩形的长和宽。 $\texttt{width} = \min(\texttt{tr}_{a_x}, \texttt{tr}_{b_x}) - \max(\texttt{bl}_{a_x}, \texttt{bl}_{b_x})$. $\texttt{length} = \min(\texttt{tr}_{a_y}, \texttt{tr}_{b_y}) - \max(\texttt{bl}_{a_y}, \texttt{bl}_{b_y})$.

如果其中任一值为负，两个矩形不相交；如果值为零，两个矩形只在一个点或一条边上 相接。将长和宽相乘即可得到重叠面积。

实现

Copy
int interArea(int[] s1, int[] s2) {
	int bl_a_x = s1[0], bl_a_y = s1[1], tr_a_x = s1[2], tr_a_y = s1[3];
	int bl_b_x = s2[0], bl_b_y = s2[1], tr_b_x = s2[2], tr_b_y = s2[3];
	return ((Math.min(tr_a_x, tr_b_x) - Math.max(bl_a_x, bl_b_x)) *
	        (Math.min(tr_a_y, tr_b_y) - Math.max(bl_a_y, bl_b_y)));
}

题目