题目算法分析

1. 问题转化

题目说：

• 骰子是均质凸多面体，重心 $O$ 已知（即所有顶点的算术平均）。
• 以 $O$ 为球心作单位球面 $S$。
• 对于每个面 $C$，在球面 $S$ 上有一个区域 $T$，如果重力方向（从重心竖直向下）与 $S$ 的交点落在 $T$ 中，则该面着地。
• 概率 = $T$ 的面积 / $4\pi$。

这实际上是在说：
球面区域 $T$ 是与该面对应的“球面多边形”，其边界是垂直于该面各条棱的大圆。

2. 球面多边形的面积公式

题目给出了球面三角形的面积公式：

$\text{Area} = \alpha + \beta + \gamma - \pi$

其中 $\alpha, \beta, \gamma$ 是三个二面角（即大圆之间的夹角）。

对于球面 $k$ 边形，其面积公式推广为：

$\text{Area} = \sum_{i=1}^k \theta_i - (k-2)\pi$

其中 $\theta_i$ 是球面多边形的第 $i$ 个内角（即相邻两个大圆平面的二面角）。

3. 如何找到每个面对应的球面多边形

对于凸多面体的一个面 $C$，它的球面区域 $T$ 实际上是：

球面上所有与面 $C$ 的法向量夹角小于 $90^\circ$ 的方向的集合吗？
这样会得到半球，但多个面共享球面。

实际上，$T$ 是球面上满足“该方向重力下，该面是唯一最低面”的区域。
对于凸多面体，这个区域是：该面的外法向量方向附近的一块区域，其边界由该面与相邻面的“平分大圆”决定。

更准确地说：
对于面 $C$ 的每条棱（与相邻面 $C'$ 共享），在球面上这两个面的外法向量之间有一个大圆弧（即两个法向量的垂直平分大圆），这个弧就是 $T$ 与相邻区域的分界线。

因此，每个面的球面区域 $T$ 是一个球面多边形，其顶点是该面的外法向量与相邻几个面的外法向量在球面上的交点。

4. 计算方法

已知每个面的多边形顶点（3D坐标），我们可以：

1. 计算每个面的单位外法向量
   用多边形的前三个顶点 $A,B,C$ 计算 $(B-A)\times(C-A)$ 得到法向量，然后归一化。注意要用外法向量（从多面体内部指向外），因为输入是逆时针（从外部看），所以叉积方向就是外法向量。

2. 球面多边形的面积
   对于面 $F$，它的球面多边形顶点就是它的外法向量 $n_F$ 以及相邻面的外法向量之间的交点吗？
   其实更简单：球面多边形的顶点是 $n_F$ 吗？不对，球面多边形的顶点是三个相邻面法向量的交点。
   但更常用的方法：
   球面多边形的顶点是该面的外法向量在球面上的点吗？不是，顶点是相邻三个面的外法向量在球面上的交点，这些交点是球面凸多边形的顶点。

   不过对于凸多面体，有一个已知结论：
   每个面的球面多边形的顶点就是相邻面的外法向量在球面上的点。
   所以对于面 $F$，它的球面多边形的顶点集合是 $\{ n_{F'} \mid F' \text{与} F \text{相邻} \}$ 按环绕顺序排列。

   但相邻关系：两个面相邻当且仅当它们共享一条棱。

3. 计算步骤：

   • 计算每个面的单位外法向量。
   • 对于每个面 $F$，找出所有与它相邻的面（通过公共边判断）。
   • 将 $F$ 的外法向量 $n_F$ 与相邻面的外法向量按顺序（按 $F$ 的棱顺序）排列，得到球面多边形的顶点序列 $V_1, V_2, \dots, V_k$（都是单位向量，在球面上）。
   • 用球面多边形面积公式：$$\text{Area} = \sum_{i=1}^k \text{atan2}( \det(V_i, V_{i+1}, V_F), V_i \cdot V_{i+1} ) $$其中 $V_F$ 是面 $F$ 的外法向量，$\det$ 是标量三重积，这个公式用于计算球面多边形的内角。 更标准的做法：球面多边形的面积 = 多边形的球面角之和 - (k-2)\pi，其中球面角用相邻顶点的大圆弧夹角计算。

   实际上，已知球面多边形顶点 $P_1, P_2, \dots, P_k$（单位向量），其面积可以用 Girard 公式的推广： $\text{Area} = \sum_{i=1}^k \theta_i - (k-2)\pi$ 其中 $\theta_i$ 是顶点 $P_i$ 处的球面角，等于 $\angle (P_{i-1}, P_i, P_{i+1})$ 在球面上的角度，可以用向量公式计算：

   $$\theta_i = \pi - \arccos\left( \frac{(P_{i-1} \times P_i) \cdot (P_i \times P_{i+1})}{\|P_{i-1} \times P_i\| \cdot \|P_i \times P_{i+1}\|} \right) $$

   但要注意符号，更可靠的是用 atan2 法。

4. 更简单的实现方法：
   用单位球面三角形面积累加：将球面多边形三角剖分（从 $V_F$ 到每对相邻顶点），用球面三角形面积公式：

   $$\text{Area} = \alpha + \beta + \gamma - \pi$$

   其中 $\alpha,\beta,\gamma$ 是三个大圆弧之间的二面角，可以用向量点积求夹角得到。

   具体：对于球面三角形 $ABC$（单位向量），面积 = $A$ 处角 + $B$ 处角 + $C$ 处角 - $\pi$，每个角可以用向量公式计算，例如角 $A$ = $\arccos\left( \frac{(A\times B)\cdot(A\times C)}{\|A\times B\|\|A\times C\|} \right)$。

5. 算法步骤总结

1. 读入 $n, f$ 和顶点坐标。
2. 计算每个面的外法向量（归一化）。
3. 建立面与面的邻接关系（通过公共边）。
4. 对每个面 $F$：
   • 收集相邻面的外法向量（按 $F$ 的棱顺序排列），这就是球面多边形的顶点序列。
   • 将球面多边形三角剖分（例如从 $n_F$ 出发到每条边）。
   • 对每个球面三角形用公式计算面积，累加得到 $T$ 的面积。
5. 概率 = $T$ 的面积 / $4\pi$。
6. 输出每个面的概率，保留 7 位小数。

6. 样例解释

样例是立方体，6 个面，每个面的球面区域面积相等 = $4\pi/6$，概率 = $1/6 \approx 0.1666667$。