# 交集分类：顶边方法

出题人解法：选择顶边最高的矩形，检查另一个矩形的顶边；配套讲解另有投影及中心距离两种方法。Codex（GPT-6）：补齐题面提示的退化分类及可执行程序，核对全部交集类型。

## 统一端点并判空

对每个图形 $X$ ，将输入规范化为闭区间的直积 $[l_X,r_X]\times[b_X,t_X]$ ，分别表示左右和上下边界。允许区间长度为零。

交换两个图形，使 $t_A\ge t_B$ . 交集为空当且仅当以下至少一个条件成立：

$$t_B<b_A\quad\text{或}\quad r_A<l_B\quad\text{或}\quad r_B<l_A$$

后两个条件检查水平区间分离。纵向只需检查第一个条件：$t_A\ge t_B\ge b_B$ 已排除另一种上下分离方式。

## 正确性

如果上式任一严格不等式成立，两图形在某个坐标方向没有公共坐标，因此不相交。反之，两个水平闭区间相交，且 $t_B$ 同时位于两个纵向闭区间内。选取任意公共水平坐标，与纵坐标 $t_B$ 组合，就得到一个公共点。故判空条件充分且必要。使用严格小于号，才能保留边界接触和点退化。

## 非空交集的维数

排除空集后，分别判断两个方向的公共区间是否具有正长度：

$$p_x=[\max(l_A,l_B)<\min(r_A,r_B)]$$

$$p_y=[t_B>b_A\ \land\ t_B>b_B]$$

方括号表示条件为真时取 $1$ ，否则取 $0$ . 由于公共纵向区间的上端点为 $t_B$ ，第二个式子恰好判断 $t_B>\max(b_A,b_B)$ .

交集是两个公共区间的直积，所以 $p_x+p_y=2$ 时为 `Area` ，等于 $1$ 时为 `Edge` ，等于 $0$ 时为 `Point` . 一维正长度与另一维零长度形成线段；两维都为零只剩一个点。这也覆盖一条线段位于矩形内部、两条线段交叉等退化情况。

不能只看输入图形的退化类型来判断交集维数：两个正面积矩形也可能只接触一条边或一个点。

## 复杂度与方案比较

每组 $O(1)$ 时间和 $O(1)$ 额外空间，全部输入为 $O(T+1)$ 时间。无需计算面积或乘坐标差；所有实现都使用 64 位整数，方便安全处理中心坐标之和。

首选程序为 [std.cpp](std.cpp)。另有两份并列方案，均具有相同的复杂度并支持完整数据：

- [对称投影公式](solution-alternative-projection.zh.md)与 [alternative-projection.cpp](alternative-projection.cpp)：不交换图形，直接求两个坐标轴上的公共区间，表达对称。
- [中心距离](solution-alternative-center.zh.md)与 [alternative-center.cpp](alternative-center.cpp)：比较中心距离与半边长之和，全部乘以二后使用整数运算。

顶边法对应题面的几何观察；投影公式无需按高低排序；中心距离法提供另一种几何表达，但组合多个坐标时需要较大的整数类型。三者没有渐进复杂度差异，不把代码长短或常数级实测波动作为算法优势。

验证包含所有取自 $\{-1,0,1\}$ 的八个端点坐标组合、端点逆序、包含、接触、退化与坐标极值。数据配方见 [plan.json](tests/plan.json)，性能见[评测说明](../../../docs/评测环境与性能.md)。