Constellation

作者：梁浩 钟知闲

关键词：概率，枚举

题目简述

给N个二维平面上的点，第i个点有p[i]的概率出现在最终结果中。问最后存在于最终结果的点所构成的凸包的面积期望是多少。 保证 $N\le 50$，$0.001\le p[i]\le 1$。

算法

如果知道最终的凸包，那么我么可以通过逆时针枚举每条边，计算原点和这两个点形成的两个向量的叉积来得到凸包的面积，考虑到在计算过程中，边与边之间没有影响， 所以我们可以枚举所有点对(A,B)，并要求边AB必须在凸包上，且逆时针顺序为AB，那么这条边的贡献就是$P(AB这条边在凸包上)*(\overrightarrow{OB} × \overrightarrow{OA})/2$。其中概率P就是边AB 左方没有点且AB间没有点，枚举判断即可。时间复杂度$O(N^3)$

优化

在枚举 $AB$ 的时候有一个小技巧：先枚举 $A$，然后将其余点按照以 $A$ 为中心的极角排序，再按顺序枚举 $B$，这样位于 $AB$ 左侧的点是环上的连续区间，且随着 $B$ 的逆时针移动，这个区间也是单调逆时针移动的，维护区间内的非零概率乘积 $P$ 以及零的个数即可，这样的枚举复杂度就降到了 $O(N^2)$。