# 矩形相交：顶边方法

出题人解法：选择顶边最高的矩形，检查另一个矩形的顶边；配套讲解另有投影及中心距离两种方法。Codex（GPT-6）：保留顶边方法，移除非标准数组初始化，使用统一的 64 位坐标。

## 统一端点并判空

对每个图形 $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$ 组合，就得到一个公共点。故判空条件充分且必要。使用严格小于号，才能保留边界接触和点退化。

## 复杂度与方案比较

每组 $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)。