核心概述：计算给定圆与逆时针多边形的交叠面积，单次扫描累加边贡献，时间 O(n)。
Description: Returns the area of the intersection of a circle with a ccw polygon. Time: O(n) Status: Tested on GNYR 2019 Gerrymandering, stress-tested
展开阐述：
-
定义与背景
- 问题：给定圆心 c、半径 r 以及按逆时针（ccw）给出的简单多边形顶点序列 ps，求圆与多边形相交区域的面积。
- 工程背景：在地理围栏覆盖评估、投票区划叠加面积、圆形影响范围与多边形边界重叠统计等场景常用。
- 接口/数据结构（据实现约定）
- circlePoly(c, r, ps)：返回 double 面积。
- P 表示点类型，需支持加减、点积/叉积、与 atan2 相关运算；ps 顶点应为 ccw 顺序。
-
核心算法流程
- 坐标平移：将多边形各点减去圆心 c，使圆心移至原点，方便使用 r 与向量叉积/点积。
- 有向角函数 arg(p, q)：以 atan2(p × q, p · q) 计算从向量 p 到 q 的有向角，范围 (-π, π]，用于扇形面积 r²·arg/2。
- 单边贡献 tri(p, q)：
- 设边 pq 的参数方程 p + t(q - p)，t ∈ [0, 1]。
- 通过解 |p + t(q - p)|² = r² 的二次方程求可能交点参数 s ≤ t（经判别式 det 检测）。
- 情况分解：
- 无交或交点不在 [0,1] 内：整段作为扇形贡献 area += r²·arg(p, q)/2。
- 有交且分段为 p→u（扇形）、u→v（弦内三角形）、v→q（扇形）， 贡献累加：r²·arg(p, u)/2 + cross(u, v)/2 + r²·arg(v, q)/2。
- 遍历多边形所有边 i：累加 tri(ps[i], ps[(i+1)%n]) 即得总面积。
- 结果为有符号面积的代数和；按 ccw 约定得到非负结果。
-
复杂度与边界条件
- 复杂度：对每条边做常数次计算，整体 O(n)。
- 边界与数值：
- 精度：浮点误差可能导致判别式 det 的微小负值，工程上常以 eps 裁剪，如 det < -eps 视为无交，|det| ≤ eps 视为相切。
- 相切：当 det≈0 时可视为出现一个交点，按扇形+零面积三角形处理。
- 顶点在圆上/边跨越圆：分段逻辑已覆盖，但需谨慎处理参数 s,t 的裁剪到 [0,1]。
- 多边形方向：要求 ccw；若输入为 cw，应先反转以确保符号一致。
- 自交或非简单多边形：实现假设简单多边形；非简单情形面积含义不再等价。
- 溢出与稳定性：
- 若点坐标为整数且值域较大，内部以 double 计算时可出现误差；如需稳健可在上游做坐标缩放或采用 long double。
-
实现细节与常见坑
- 使用 atan2 计算有向角避免数值不稳定的 acos。
- 使用 cross(u, v)/2 表示弦内三角形面积（以原点为第三点），注意符号与顶点顺序一致性。
- 对交点参数求解时，需保证按升序分配 u、v，使分段顺序一致。
- 输入 ps 必须首尾相连视为简单闭合多边形，边索引使用 (i+1)%n。
-
变体与扩展
- 圆与多边形周长交长：可用类似分段思想计算圆弧长度与线段内段长度。
- 多圆与多边形的联合面积：可通过容斥或扫描弧段/边段合并，复杂度与实现显著提升。
- 三维推广（球与多面体）：思路可借鉴，但需要球面三角与曲面片面积公式。
-
正确性要点与不变式
- 整体由扇形面积与三角形面积分段组成，边—圆交关系的分类完备。
- ccw 方向保证分段面积的符号一致；arg 的有向角与 cross 的符号相容。
- 每条边贡献相加即为圆与多边形交区域的有向面积，无重叠遗漏。
-
对比与取舍
- 与019-几何-圆与圆相交、020-几何-圆与直线相交相比，本法面向“多边形整体”，避免枚举所有交点后再做复杂区域合并。
- 与多边形裁剪再求面积的通用框架相比，本实现更简洁高效但专用于圆这一特殊曲线。