凸包面积相关-拓冰建站

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]。