#P4080. [SDOI2016] 平凡的骰子

[SDOI2016] 平凡的骰子

题目描述

这是一枚平凡的骰子。它是一个均质凸多面体,表面有n个端点,有f个面,每一面是一个凸多边形,且任意两面不共面。将这枚骰子抛向空中,骰子落地的时候不会发生二次弹跳(这是一种非常理想的情况)。

你希望知道最终每一面着地的概率。每一面着地的概率可以用如下的方法计算:我们假设O为骰子的重心,并以O为球心,做半径为1的单位球面(记为S)。

我们知道S的表面积即单位球的表面积,为4*pi,这里pi为圆周率。对于骰子的某一面C来说,球面S上存在一块区域T满足:当下落时若骰子所受重力方向与S的交点落在T中,则C就是最终着地的一面。那么C着地的概率为区域T的面积除以4*pi。

为了能更好地辅助计算球面上一块区域的面积,我们给出单位球面S上三角形的面积计算公式。考虑单位球面S上的三个两两相交的大圆,交点依次为A,B和C。则曲面三角形ABC的面积为 Area(ABC)=α+β+γπ\text{Area}(ABC)=\alpha+\beta+\gamma-\pi,其中 α,β,γ\alpha,\beta , \gamma 分别对应了三个二面角的大小。如下图所示。

我们保证:每一面着地的时候,重心的垂心都恰好在这一面内。也就是说不会出现摆不稳的情况。

输入格式

第一行输入两个整数,分别表示端点总数n与表面总数f,分别从1开始编号。

之后n行,每行有三个浮点数x,y和z,给出了每一个端点的坐标。

之后f行依次描述了每一块表面,首先给出不小于3的整数d,表示这一面的端点个数,之后d个整数按照逆时针方向(视角在骰子的外面)给出了每一个端点的编号。

输出格式

输出f行,第i行有一个浮点数,表示第i个面着地的概率。本题中您的输出应该保留距离答案最近的7位小数,即在需要保留7位小数的前提之下与标准答案最接近。数据保证可以避免对小数点后第八位四舍五入后产生的精度误差

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<=50且4<=m<=50,所有坐标的绝对值都在10000以内