#P4603. [Sdoi2016]平凡的骰子

    ID: 1360 传统题 1000ms 512MiB 尝试: 143 已通过: 72 难度: 8 上传者: 标签>难度分类提高+/省选-计算几何叉积点积四面体分解求多面体重心球面盈量公式CF2400

[Sdoi2016]平凡的骰子

[SDOI2016] 平凡的骰子

题目描述

一枚骰子是均质凸多面体,有 nn 个顶点、ff 个面。每个面都是凸多边形,任意两个面不共面。将骰子抛向空中,假定落地后不会发生二次弹跳。求每个面最终着地的概率。

设 OO 为骰子的重心,SS 为以 OO 为球心、半径为 11 的球面。对某一面 CC,重力方向对应从 OO 出发的射线。若该射线在 SS 上的交点位于从 OO 观察面 CC 所对应的球面区域 TT 内,则 CC 最终着地。该面的着地概率为 TT 的面积除以 4π4\pi。

单位球面上,若球面三角形 ABCABC 的内角为 α,β,γ\alpha,\beta,\gamma,其面积为

Area⁡(ABC)=α+β+γ−π.\operatorname{Area}(ABC)=\alpha+\beta+\gamma-\pi.

单位球面上的球面三角形和内角

保证骰子以任意一面着地时,重心在该面上的垂直投影落在该面内。

输入格式

第一行两个整数 n,fn,f,分别为顶点数和面数,均从 11 开始编号。

接下来 nn 行,每行三个实数 x,y,zx,y,z,表示该顶点的坐标。

再接下来 ff 行。每行先给出整数 d≥3d\ge3,再给出 dd 个顶点编号,按从骰子外侧观察该面时的逆时针顺序列出。

输出格式

输出 ff 行,第 ii 行是第 ii 个面着地的概率。将结果舍入到最接近的七位小数,并恰好输出小数点后七位。数据保证可以避免小数点后第八位舍入时的精度歧义。

8 6
1 0 0
1 1 0
1 0 1
1 1 1
0 0 0
0 1 0
0 0 1
0 1 1
4 1 2 4 3
4 2 6 8 4
4 6 5 7 8
4 5 1 3 7
4 3 4 8 7
4 1 5 6 2
0.1666667
0.1666667
0.1666667
0.1666667
0.1666667
0.1666667

数据范围

4≤n≤504\le n\le50,4≤f≤504\le f\le50,所有坐标的绝对值均不超过 10410^4。

  • 有 20%20\% 的数据,骰子是长方体。
  • 另有 20%20\% 的数据,骰子是四面体。
  • 再有 30%30\% 的数据,每个面都是三角形。