Problem1047--#2070. 「SDOI2016」平凡的骰子

1047: #2070. 「SDOI2016」平凡的骰子

Time Limit: 1 Sec  Memory Limit: 256 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

这是一枚平凡的骰子。它是一个均质凸多面体,表面有 nnn 个端点,有 fff 个面,每一面是一个凸多边形,且任意两面不共面。将这枚骰子抛向空中,骰子落地的时候不会发生二次弹跳(这是一种非常理想的情况)。你希望知道最终每一面着地的概率。每一面着地的概率可以用如下的方法计算:我们假设 OOO 为骰子的重心,并以 OOO 为球心,做半径为 111 的单位球面(记为 SSS)。我们知道 SSS 的表面积即单位球的表面积,为 4π4\pi4π,这里 π\piπ 为圆周率。对于骰子的某一面 CCC 来说,球面 SSS 上存在一块区域 TTT 满足:当下落时若骰子所受重力方向与 SSS 的交点落在 TTT 中,则 CCC 就是最终着地的一面。那么 CCC 着地的概率为区域 TTT 的面积除以 4π4\pi4π。为了能更好地辅助计算球面上一块区域的面积,我们给出单位球面 SSS 上三角形的面积计算公式。考虑单位球面 SSS 上的三个两两相交的大圆,交点依次为 AAABBBCCC。则曲面三角形 ABCABCABC 的面积为 Area(ABC)=α+β+γ−π\text{Area}(ABC)=\alpha+\beta+\gamma-\piArea(ABC)=α+β+γπ,其中 α\alphaαβ\betaβγ\gammaγ 分别对应了三个二面角的大小。如下图所示。

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

输入格式

第一行输入两个整数,分别表示端点总数 nnn 与表面总数 fff,分别从 111 开始编号。
之后 nnn 行,每行有三个浮点数 xxxyyyzzz,给出了每一个端点的坐标。
之后 fff 行依次描述了每一块表面,首先给出不小于 333 的整数 ddd,表示这一面的端点个数,之后 ddd 个整数按照逆时针方向(视角在骰子的外面)给出了每一个端点的编号。

输出格式

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

样例

样例输入

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 \leq n \leq 504n504≤f≤804 \leq f \leq 804f80,所有坐标的绝对值都在 100001000010000 以内。

Source/Category