🔍 核心思路：从概率到几何

题目要求点 $P$ 与凸 $n$ 边形顶点连成的 $n$ 个三角形中，三角形 $P P_0 P_1$ 面积最小的概率。

1. 概率表示为面积比 由于点 $P$ 在凸多边形内随机分布，正确站位概率 = 满足条件的区域面积 / 凸多边形面积。

2. 将面积条件转化为不等式 需要三角形 $P P_0 P_1$ 的面积 ≤ 三角形 $P P_i P_{i+1}$ 的面积（对于 $i$ 从 $1$ 到 $n-1$）。注意索引循环，$P_n$ 即 $P_0$。 三角形面积可通过向量叉积计算。对于点 $P(x, y)$，三角形 $P A B$ 的面积为向量 $\overrightarrow{PA}$ 与 $\overrightarrow{PB}$ 叉积绝对值的一半。由于凸多边形顶点逆时针排列，在不等式比较时可忽略绝对值，保留叉积的符号。

3. 构建半平面 每个面积比较条件 $S_{\triangle P P_0 P_1} \leq S_{\triangle P P_i P_{i+1}}$ 都可以转化为一个关于 $P(x, y)$ 的线性不等式，形式为 $A x + B y + C \leq 0$。这个不等式定义了满足条件的一个半平面。 凸多边形本身也对应 $n$ 个半平面（每条边所在的直线将平面划分为两部分，我们需要包含多边形内部的那一侧）。

4. 求解可行域 所有上述半平面（$n-1$ 个由面积不等式产生，$n$ 个由凸多边形边界产生）的交集，就是点 $P$ 所有可能的位置区域，即可行域。 这个可行域也是一个凸多边形。我们可以通过半平面交算法求出这个可行域，并计算其面积。

5. 计算概率 最终概率 = 可行域面积 / 原凸多边形面积。

🧮 关键步骤：不等式推导

以 $S_{\triangle P P_0 P_1} \leq S_{\triangle P P_i P_{i+1}}$ 为例，推导过程如下：

1. 向量 $\overrightarrow{P_0 P} = (x - x_0, y - y_0)$， $\overrightarrow{P_0 P_1} = (x_1 - x_0, y_1 - y_0)$。 三角形 $P P_0 P_1$ 的面积（叉积形式）为：

   $$S_{\triangle P P_0 P_1} = \frac{1}{2} |(x - x_0, y - y_0) \times (x_1 - x_0, y_1 - y_0)| $$

   去掉绝对值和不影响不等式的系数 $\frac{1}{2}$，我们关注叉积本身：

   $$(x - x_0)(y_1 - y_0) - (y - y_0)(x_1 - x_0)$$

2. 同理，对于三角形 $P P_i P_{i+1}$，其叉积为：

   $$(x - x_i)(y_{i+1} - y_i) - (y - y_i)(x_{i+1} - x_i) $$

3. 将 $S_{\triangle P P_0 P_1} \leq S_{\triangle P P_i P_{i+1}}$ 转化为：

   $$(x - x_0)(y_1 - y_0) - (y - y_0)(x_1 - x_0) \leq (x - x_i)(y_{i+1} - y_i) - (y - y_i)(x_{i+1} - x_i) $$

4. 展开并整理成 $A x + B y + C \leq 0$ 的形式：

   $$[(y_1 - y_0) - (y_{i+1} - y_i)]x + [-(x_1 - x_0) + (x_{i+1} - x_i)]y + [(x_0 y_1 - y_0 x_1) - (x_i y_{i+1} - y_i x_{i+1})] \leq 0 $$

   这样就得到了所需的半平面方程。

⚙️ 算法实现与细节

1. 半平面交算法 使用标准的半平面交算法（如排序增量法）。主要步骤：

   • 直线表示：用方向向量或点向式表示直线，注意方向，确保半平面在直线左侧。
   • 按极角排序：将半平面按直线极角排序，极角相同的保留左侧范围最大的一个。
   • 双端队列维护：用双端队列维护当前半平面交的边界，依次加入新的半平面，检查队首和队尾的交点是否在新半平面外，否则弹出。
   • 计算面积：最后队列中的半平面围成的凸多边形就是可行域，计算其面积。

2. 注意事项

   • 精度问题：坐标范围大，计算叉积、交点时使用 double 并注意精度控制，可考虑 eps 取 $10^{-10}$ 量级。
   • 边界处理：原凸多边形的 $n$ 条边对应的半平面也需要加入计算。
   • 退化情况：注意半平面交可能为空或为凸多边形。

💎 总结

这道题的解题脉络是：

1. 将概率问题转化为几何面积问题。
2. 将面积比较条件转化为线性不等式，定义半平面。
3. 利用半平面交算法求所有约束条件的交集，得到可行域面积。
4. 计算面积比得到最终概率。

这种将代数不等式与几何图形结合的思想，以及半平面交算法的应用，是解决此类问题的关键。