题意简述：

在一个格点图中 给定一个凸$n$边形（每个定点均在格点上），随机选择其中一些点构成一个子多边形，

求子多边形的内部点个数的期望。

----------------------------------------------------------------------------------------------------------------------------------

首先这题是需要知道 皮克定理 这个结论的

我们用 $s$代表多边形面积 $ans$代表内部点数（即要求的答案）$node$代表边上的格点

公式即为 $ans=s-\frac{node}{2}+1$

----------------------------------------------------------------------------------------------------------------------------------

然后这题是求期望的 对于期望 我们知道它是满足分配率的 于是我们可以考虑分别求出$s$和$node$的期望

对于$s$的期望 可以这样考虑（算贡献）

每次选出一个子多边形后 剩余部分显然是可以用多个顶点连续的多边形补成的

我们可以用前缀和维护这个顶点连续的多边形的面积 然后来算贡献

公式为$\displaystyle \frac{2^{n-i} -1}{2^n-1-n-C_2^n}*$子多边形面积

 

直接求出所有是$O(n^2)$的 然而观察公式我们可以发现i取较大的数的时候对答案的影响是很小的

综合考虑题目要求的$10^{-9}$的相对误差以及$double$的精度 $i$的上界$lim$可以取$min(n,60)$

$node$的求法也是类似的 只要熟悉如何算贡献就比较容易了 想了很久还不懂的话可以留言

----------------------------------------------------------------------------------------------------------------------------------

这样我们就可以过掉样例了 然后我们会$ WA  10$

因为$double$不仅仅是精度限制 还有范围限制 大概范围就是 $(10^{300}～10^{-300})$

这个问题 初次遇见还是很纠结的 多想想后 我们发现可以把公式变形成这样(上下同时除$2^n$):

$\displaystyle\frac{2^{-i} -1}{1-2^{-n}*(1+n+C_n^2)}*$子多边形面积

----------------------------------------------------------------------------------------------------------------------------------

差不多就是这些了 第一次写$div1D$题 还有些小激动呢

#include 
     
      #include 
      
       #include 
       
        using namespace std;const int N=1e5+10;double polygon[N],p[N];int x[N],y[N];double s,ans,node,product;int n,lim;double cross(long long x1,long long y1,long long x2,long long y2){    return x1*y2-x2*y1;}int main(){    scanf("%d",&n);    lim=min(n,60);    p[0]=1;    for(int i=0;i