题目大意
给一个点集,每个点出现的概率都为p,求期望只在结点处相交最多能连多少条边。
解题思路
欧拉公式:在一个平面图内,设点数为V,边数为E,有界面数为F一定满足:V+F-E=1。
将点三角剖分,一定是最优,这时2E=3F+K,K为凸包上边的条数。
整理得E=3V-K-3。由于期望的线性性,点的期望为N*p,凸包上边的期望等于每条边在凸包上期望的和,枚举一条边,张一个最大小于180度的角,中间的点可选可不选,外侧的点一定不选,统计答案即可。
注意V=0时K=0,不满足公式,加上3*这种情况出现的概率。
code
using namespace std;
int const Mxn=1000+9,Mo=1e8+7;
LL N,P,Pow[Mxn];
struct Rec{
LF X,Y;
Rec(LF XX=0,LF YY=0){
X=XX;Y=YY;
}
};
bool Cmp(Rec X,Rec Y){
return atan2(X.Y,X.X)<atan2(Y.Y,Y.X);
}
Rec operator-(Rec X,Rec Y){
return Rec(X.X-Y.X,X.Y-Y.Y);
}
LF Cross(Rec X,Rec Y){
return X.X*Y.Y-X.Y*Y.X;
}
Rec A[Mxn],B[Mxn];
int main(){
//freopen("forgive.in","r",stdin);
//freopen("forgive.out","w",stdout);
freopen("d.in","r",stdin);
freopen("d.out","w",stdout);
scanf("%lld%lld",&N,&P);
Fo(i,1,N)scanf("%lf%lf",&A[i].X,&A[i].Y);
Pow[0]=1;
Fo(i,1,N)Pow[i]=Pow[i-1]*(1-P+Mo)%Mo;
LL Ans=3*N*P%Mo-3;
Fo(i,1,N){
int Tmp=0,k=1;
Fo(j,1,N)if(i!=j)B[++Tmp]=A[j]-A[i];
sort(B+1,B+N,Cmp);
LF x1=atan2(1,-1),x2=atan2(0,-1);
Fo(j,1,N-1){
while((Cross(B[j],B[((k==N-1)?1:k+1)])>0)&&(((k==N-1)?1:k+1)!=j))
k=(k==N-1)?1:k+1;
Ans=(Ans-Pow[N-(((k<j)?k+N-1:k)-j+2)]*P%Mo*P)%Mo;
if(j==k)k=(k==N-1)?1:k+1;
}
}
printf("%lld",((Ans+3*Pow[N])%Mo+Mo)%Mo);
return 0;
}