1. 凸包面积计算（叉积法与鞋带公式）
1.1 核心公式
对于按逆时针顺序排列的凸包顶点 \(P_0, P_1, \dots, P_{n-1}\)，其面积 \(S\) 为：
\[S = \frac{1}{2} \left| \sum_{i=0}^{n-1} (x_i y_{i+1} - x_{i+1} y_i) \right|
\]
其中 \(P_n = P_0\)（闭合回路）。
1.2 几何意义（三角剖分）
公式本质是将多边形以原点为公共顶点剖分为若干三角形，叉积 \(x_i y_{i+1} - x_{i+1} y_i\) 表示平行四边形（三角形两倍）的有向面积。
1.3 符号含义
- 逆时针（CCW）：\(\sum > 0\)。
- 顺时针（CW）：\(\sum < 0\)。
- 外部无限面：在有界面追踪中，其有符号面积为负，用于定位对偶图根节点。
2. Andrew 单调链凸包算法
2.1 核心思想
将点集按 \(X\) 轴（若相同则按 \(Y\) 轴）排序，分别构建下链（Lower Hull）和上链（Upper Hull）。
2.2 叉积判转向
对于三点 \(A, B, C\)：
\[\text{cross}(A,B,C) = (B-A) \times (C-A)
\]
- \(\text{cross} > 0\)：左转（逆时针），保留。
- \(\text{cross} \le 0\)：右转或共线，弹出栈顶（剔除凹点或共线点）。
2.3 复杂度
- 时间复杂度：\(O(n \log n)\)（瓶颈在排序）。
- 空间复杂度：\(O(n)\)。
3. 平面图转对偶图（DCEL 半边结构）
3.1 映射关系
| 原图 \(G\) | 对偶图 \(G^*\) | 映射规则 |
|---|---|---|
| 一个面 \(f\) | 一个顶点 \(v^*\) | 每个面对应一个点（包含外部无限面） |
| 一条边 \(e\) | 一条边 \(e^*\) | 若边 \(e\) 左侧是 \(f_1\)，右侧是 \(f_2\)，则 \(e^*\) 连接 \(f_1^*\) 和 \(f_2^*\) |
3.2 半边数据结构（Half-Edge）
每条无向边拆分为两条有向半边（Half-Edge），各存储：
from/to：起点/终点索引。twin：反向半边 ID（可通过id ^ 1快速获取）。next：面追踪的下一条半边。face：该有向半边左侧所属的面编号。
3.3 ID 映射规则（奇偶配对）
对于第 \(i\) 条输入无向边（edge_id = i）：
- 方向 \(a \to b\) 的半边 ID：
he = 2 * i - 方向 \(b \to a\) 的半边 ID：
he = 2 * i + 1 - 反向查找：
twin = he ^ 1 - 原边查找：
edge_id = he / 2
4. 极角排序与面遍历（Face Traversal）
4.1 极角排序规则
使用 atan2(y, x) 计算方向向量与 \(X\) 轴正方向的夹角（范围 \([-\pi, \pi]\)）。
- 升序排序：角度从小到大 => 逆时针方向。
- 排序稳定性：对于共线边（角度相同），需按终点编号
to或边 ID 作为第二关键字，满足 STL 的严格弱序，确保lower_bound精确定位。
4.2 Next 指针构建（--kl 规则）
对于有向边 \(i\)：\(u \to v\)，在顶点 \(v\) 的出边中：
- 查找反向边 \(v \to u\)（即
e[i ^ 1]）的位置kl。 - 取前一条边
--kl（循环意义下）作为nxt[i]。
几何意义：
- 反向边角度为 \(\theta_{back} = \theta_{forward} + \pi\)。
- 取前一条（角度更小）使得 \(\theta_{forward} < \theta_{next} < \theta_{forward} + \pi\)。
- 结论：相对于当前前进方向，身体向左转（逆时针），从而追踪出逆时针方向的内部有界面。
4.3 外部无限面判定
面遍历结束后，所有内部有界面按逆时针追踪，鞋带公式计算结果 \(s > 0\)；外部无限面按顺时针，计算结果 \(s \le 0\)。
5. 有符号面积计算（叉积累加）
5.1 平移基准点（数值稳定）
代码中采用基准点 \(P_{start}\)（面的起点）平移：
\[s_{\text{face}} = \sum (P_j - P_{start}) \times (P_{j+1} - P_{start})
\]
其中 \(\times\) 为叉积。平移后面积不变，但数值更小，防止溢出。
5.2 缩放因子（HNOI2016 经典处理）
- 原始面积为 \(A\)。
- 存储的叉积和 \(s_{\text{face}} = 2A\)（未除以 2）。
- 子树 DFS 初始化：
- 分子（矿量）\(s2[x] = s[x]^2 = (2A)^2 = 4A^2\)。
- 分母（面积）\(s[x] \ll= 1 \Rightarrow s[x] = 4A\)。
- 结果：分子分母均有公因子 4，最终 \(\gcd\) 约分后抵消，输出精确最简分数。
6. 对偶图生成树与树上差分（查询逻辑）
6.1 子树贡献预处理
以外部无限面（\(s \le 0\)）为根，在对偶图上 DFS 建生成树。
s[x]：子树中所有面面积的 \(4\) 倍之和。s2[x]：子树中所有面面积平方的 \(4\) 倍之和。
6.2 查询边界累加（括号匹配）
对于查询多边形的每条有向边 \(cur\)（由输入逆时针顺序确定）：
- 获取该有向边左侧面
L = fac[cur]，右侧面R = fac[cur ^ 1]。 - 若为非树边（
!in_t[cur]），跳过。 - 确定父子关系（深度大的为子节点
son）。 - 加减规则：
- 若左侧面
L == son（进入子树）：ans += sum[son]。 - 若左侧面
L == fa（离开子树）：ans -= sum[son]。
- 若左侧面
本质：这是格林公式（离散旋度）在生成树上的投影，通过边界积分圈定内部区域。