核心概述：使用鞋带公式在线性时间计算简单多边形的两倍有向面积，方向决定符号，支持整数/浮点坐标。
Description: Returns twice the signed area of a polygon. Clockwise enumeration gives negative area. Watch out for overflow if using int as T! Status: Stress-tested and tested on kattis:polygonarea
展开阐述
- 定义与背景
- 定义：设顶点按顺序 v[0..n-1] 给出（首尾相连），两倍有向面积 area2 = Σ v[i]×v[i+1]，其中 × 为二维叉积，v[n] 视为 v[0]。
- 几何含义：有向面积的符号与顶点顺序一致——ccw 为正，cw 为负。实际面积为 |area2|/2。
- 适用场景：基础几何度量（面积/质心/转动惯量的前置量）、几何布尔的区段贡献累计、栅格/栅线覆盖估计等。
- 能力边界：默认假设简单多边形（无自交）。自交多边形时该值等价于“代数面积”，不再等于几何并域面积。
- 接口/数据结构（据实现）
- 模板签名：template
T polygonArea2(vector<Point >& v) - 返回：两倍有向面积（同类型 T）。若需实际面积，使用 abs(area2)/2。
- 类型约定：
- T = int/long long：适合格点/整数输入，注意叉积中间值可能溢出 32 位；建议 long long，必要时用内置 128 位过渡。
- T = double/long double：适合连续坐标，需统一 eps 做近零判断。
- 模板签名：template
- 核心流程/要点（鞋带公式）
- 线性遍历：初始化 a = v.back().cross(v[0])；循环 i=0..n-2 累加 v[i].cross(v[i+1])。
- 首尾闭合：确保包含边 (v[n-1], v[0]) 的贡献。
- 符号与方向：输入为 ccw 则 a>0，为 cw 则 a<0；反转点序会改变符号但不影响 |a|。
- 输出与单位：area = |a|/2；两倍面积避免了中间除法，便于与整型配合。
- 复杂度与边界条件
- 复杂度：O(n) 时间，O(1) 额外空间。
- 边界：
- n<3：退化为 0（无面积）。
- 重复顶点/共线中间点：不影响正确性，但会引入冗余运算；可在上游去重/压缩。
- 自交多边形：返回代数面积；若需几何并域面积，改用扫描/布尔运算或参见045-几何-多边形并。
- 数值与溢出：
- 整数：叉积为乘加，坐标接近上界时可能溢出 64 位；可用内建 128 位中间变量或缩放。
- 浮点：累计误差与点数线性相关；高精度需求可使用 long double。
- 变体/扩展
- 面积与方向检测：通过 area2 的符号快速判断顶点顺序，必要时统一为 ccw（便于与其他模块符号一致）。
- 三角形分解：area2 亦等价于 Σ cross(v[i], v[i+1])，与以原点为参考的三角形代数面积相同，便于与043-几何-多边形重心共用。
- 带洞/多多边形：对每个环分别计算 area2，并以外环正、内环负的约定求和。
- 体素/栅格近似：当输入来自栅格边界时，鞋带公式仍有效；注意坐标单位换算。
- 正确性要点与不变式
- 叉积恒等式：cross(u, v) 等于由 u、v 构成平行四边形的有向面积，半数即三角形面积；环上累加即全多边形。
- 方向一致性：统一 ccw 可避免后续（重心、切割、布尔）中符号不一致。
- 闭合不变式：显式包含最后一条边，保持“环闭合”的面积完备性。
- 与相邻技术的对比与取舍
- 与格点皮克定理对比：鞋带公式适用于任意实坐标；皮克定理限于整点多边形且需边界/内部格点计数。
- 与扫描线/布尔区域面积：鞋带用于单个简单多边形；多个多边形并域面积参见045-几何-多边形并的扫描/覆盖方案。
- 与043-几何-多边形重心：两者共享边叉积累加；先得 area2 再得重心分母可减少重复计算。
关联节点