题解 P13946【[EC Final 2019] Moon】
Diaоsi
·
·
题解
Moon
\color{maroon}{\textsf{Very Hard}}
单位球面上有固定点 a_1,\dots,a_n，以及一个均匀随机点 a_0。若存在一个半球包含所有点 a_0,\dots,a_n，则 f=1，否则 f=0。求 \mathbb{E}[f]。
0\leq n\leq 10^5。
特判共线/共面的情况，接着对变换前的点求三维凸包，若 O 严格在凸包内，则答案为 0。
否则，求答案等价于求球面凸包的面积。遍历三维凸包的每个面，若该面不包含 O，则将这个球面三角形的面积计入答案，因为它关于 O 对称的面中如果出现了 a_0 一定有 f=0。
球面三角形的计算方式为 \alpha + \beta + \gamma - \pi，其中 \alpha,\beta,\gamma 为球面两条边与 O 构成的两个平面的二面角，可以用法向量叉乘 + 反三角函数算出。
本题究极卡精度（见 #2069），求凸包的部分需要实现全整；求二面角的部分的最大中间量达到了 10^{48}，__int128 无法存下，但是可以在容忍一点精度损失的情况下转成 long double。
注意算反三角的时候需要转化成 \tan^{-1} 而不是 \cos^{-1}，因为 \cos \in [-1,1]，压缩值域会造成大量精度损失。
时间复杂度 \mathcal{O}(n\log n)。
提交记录