📐 第十部分：计算几何

点、向量、多边形与凸包——用叉积武装起来的另一类思维题。USACO Gold/Platinum 几何题的完整工具箱。

📚 1 章 · ⏱️ 预计 1-2 周 · 🎯 目标：USACO Gold → Platinum

第十部分：计算几何

预计用时：1-2 周

计算几何从数学部分独立成篇：它的思维方式（向量、叉积、凸性）与数论/组合计数截然不同，值得单独一条学习路径。本部分从一道围栏问题出发，自底向上搭建几何工具箱。

涵盖的主题

小节	主题	核心思想
10.1.1 🥇	向量：计算几何的积木	点积、叉积与方向判定
10.1.2 🥇	常用判定：相交与距离	线段相交、点到线段距离
10.1.3 🥇	多边形：面积与点包含	鞋带公式、射线法
10.1.4 🥇	凸包：Andrew 算法	极角排序 + 单调栈，O(N log N)
10.1.5 🥇	旋转卡壳：凸包直径	对踵点对，O(N)
10.1.6 🥇	实战：围栏问题完整程序	把工具箱串起来

学习路线

10.1.1-10.1.2 是地基——叉积的正负号是后续所有判定的引擎，必须先吃透。
10.1.3-10.1.4 是 Gold 几何题主战场——凸包是 USACO 几何题最常见的第一步。
10.1.5 面向 Platinum——旋转卡壳出题频率不高，但一旦出现几乎必有它。
10.1.6 是验收——完整程序走一遍，确认每个判定函数都能默写。

复杂度速查

操作	方法	时间复杂度
向量叉积 / 方向判定	cross	O(1)
两线段是否相交	快速排斥 + 跨立实验	O(1)
多边形面积	鞋带公式	O(N)
点是否在多边形内	射线法	O(N)
凸包	Andrew 单调链	O(N log N)
凸包直径（最远点对）	旋转卡壳	O(N)

本部分学习建议

优先整数字符串技巧——叉积、面积、判定全部用 long long 整数运算可避免一切精度问题；坐标是实数时才退回 double + eps。
几何代码最怕精度——每道例题都标注了精度处理方式，写浮点几何前先看各小节的 ⚠️ 常见错误。
凸包模板要练到能默写——Andrew 算法只有十几行，但排序方向、while 弹栈条件写错一个符号就全盘崩塌。
先修知识：第 3.3 章（排序）与第 3.5 章（栈）会让 Andrew 算法的学习更顺畅，但不是硬性前置。