叉积是判断线段相交最稳定轻量的工具，通过端点相对于对方直线的两侧关系判定，需同时检查两组端点方向并处理共线重叠及浮点误差。
用叉积判断线段方向关系是核心
两条线段相交，本质是它们的端点分别位于对方所在直线的两侧（或至少一个端点在线段上）。C++里不依赖浮点几何库时，cross_product 是最稳定、最轻量的判断工具。它避免了除法和角度计算，也绕开了斜率无穷大问题。
对向量 v1 = (x1, y1) 和 v2 = (x2, y2)，叉积定义为 x1 * y2 - x2 * y1。结果正负号表示相对方向，零表示共线。
- 若
cross_product(a->b, a->c)与cross_product(a->b, a->d)异号，则点c和d在直线ab两侧 - 若其中一值为 0，说明对应点在直线
ab上，需进一步判断是否在线段ab内部（用点积或坐标范围） - 必须对两组端点都做这个检查：即
ab相对于cd，以及cd相对于ab
处理共线但不重叠的边界情况
叉积全为 0 时，四点共线，此时相交与否取决于线段是否在同一直线上且有重叠部分。很多人只检查叉积就返回 false，漏掉这种情形。
判断共线重叠的关键是：投影到 x 或 y 轴（选非恒定轴），再看区间是否有交集。例如，若 ab 和 cd 共线，可比较 min(ax, bx) 与 max(cx, dx) 等四个端点坐标。
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
立即学习“C++免费学习笔记（深入）”；
- 优先用
std::minmax获取每条线段的 x 和 y 坐标范围 - 若 x 方向区间无重叠（
max(ax,bx) 或反之），直接不相交 - 若 x 重叠但 y 不重叠（比如竖直线），则换用 y 坐标判断
- 也可统一用点积符号判断点是否在线段上：
dot(c-a, b-a) >= 0 && dot(c-b, a-b) >= 0表示c在ab上（含端点）
浮点误差下的 robust 实现要点
用 double 时，叉积接近 0 并不等于 0。直接写 == 0 会误判。必须引入容差（tolerance），但容差也不能过大，否则把本不相交的线段判成相交。
- 推荐用相对容差 + 绝对容差组合：
abs(val) - 常见错误是只设固定
eps = 1e-9，在坐标值达1e6量级时完全失效 - 若输入坐标是整数，坚持用
long long计算叉积（如(x1-x0)*(y2-y0) - (x2-x0)*(y1-y0)），彻底规避浮点误差 - 注意溢出：坐标范围超
1e9时，long long可能不够，需用__int128（GCC）或分段判断
完整判断函数怎么组织才不容易错
把方向判断和共线处理拆成两个独立辅助函数，比堆在一个函数里更易验证和复用。主逻辑应清晰体现“先判方向，再处理共线”这一流程。
- 写
orientation(p, q, r)返回-1（顺时针）、1（逆时针）、0（共线）——这是标准命名习惯，方便查资料 - 写
on_segment(p, q, r)判断q是否在线段pr上（仅在orientation == 0时调用） - 主函数
segments_intersect(a, b, c, d)先算四个 orientation 值，再按逻辑分支返回，避免嵌套过深 - 测试用例必须覆盖：正常相交、端点相交、共线重叠、共线不重叠、平行不重叠、几乎相交但因误差不交
共线重叠和浮点容差这两处，是实际项目中最常返工的地方。别跳过手动验算几个边界点坐标。
