NOI2017模拟 原谅（凸包+数学期望）

发表于 |
字数统计: 1,230字 | 阅读时长 ≈ 6min

【NOI2017模拟】原谅

问题描述

终其一生，我们在寻找一个原谅。

犯下了太多错，要原谅的那个人，永远都是自己。

Samjia在深夜中望见了没有边界的人生，他没有想到过自己犯下了这么多的错误，他想在他的一生中寻求一个原谅。

他的人生是一个没有边界的平面，平面上有n个错误，每个错误是一个点，每个点i有一定的坐标(x[i],y[i])，有一个参数p 表示每个点有p的概率出现在平面上，注意两个不同的点的出现互相没有影响，Samjia可以在两个点之间连一条线段，两条线段不能在除了端点以外的地方相交，现在Samjia想知道他最多可以连的线段数的期望。

温馨提示：请看最后面的提示：）

本题的答案在mod 100000007意义下计算

输入格式

第一行两个正整数n和p表示平面上有n个点以及每个点出现概率为p

接下来n行第i行两个实数x[i]和y[i]表示一个点的坐标

保证不存在三点共线

输出格式

一行一个正整数表示Samjia最多可以连的线段数的期望

样例输入

3 10000001

0 1

1 0

0 0

样例输出

39000003

提示：

数据中的p为0.3

1×3×(0.3×0.3×0.7)+3×0.3×0.3×0.3=0.27

贡献为1的情况有三种

贡献为3的情况有一种

对于20%的数据，p=1,1<=n<=5

对于40%的数据，p=1,1<=n<=1000

对于70%的数据，1<=n<=200

对于100%的数据，1<=n<=1000

坐标的绝对值小于等于10^4

保证0<=p<100000007

欧拉公式

在一个平面图内，设点数为V，边数为E，有界面数为F

一定满足：V+F-E=1

首先考虑对于一个给定的图，如何连边是最优的，答案是先求出凸包，然后从凸包上一个点往其他凸包上的点连边，然后做三角剖分就是最优解。

然后可以得到边数和凸包上的点存在关系。假设凸包上有$k$个点，总共有$V$个点，$E$条边，那么可以得到
$$
E=k+(k-3)+3(V-k)=3V-k-3
$$
那么我们有$E(E)=3E(V)+E(k)-3$

那么问题变成如何求期望点数和凸包上期望点数，$E(V)$很好求，主要考虑$E(k)$

注意到凸包上的点数可以通过规定边的方向从而等效于凸包上的有向线段数量。

那么我们考虑求出每条有向线段在凸包上的概率，这个比较容易求，只要求在他外边的点都不出现且两个端点出现就行了。然后就可以极角排序之后算一算了。

最后注意到当所有点都没出现的时候，会多减一个$3$，加回去就行了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define N 2005
#define int long long
using namespace std;
const double eps=1e-10;
const int mod=100000007;
int n,p[N],q[N],ans,tot;
int add(int x,int y){x+=y;return x>=mod?x-mod:x;}
int sub(int x,int y){x-=y;return x<0?x+mod:x;}
int mul(int x,int y){return 1ll*x*y%mod;}
struct node{double x,y,angle;}P[N],T[N];
bool operator<(node a,node b){return a.angle<b.angle;}
node operator+(node a,node b){return (node){a.x+b.x,a.y+b.y};}
node operator-(node a,node b){return (node){a.x-b.x,a.y-b.y};}
double operator*(node a,node b){return a.x*b.y-a.y*b.x;}
void Work(int x)
{
	int i,j,k,cnt;tot=0;
	for(i=1;i<=n;i++)if(i!=x)T[++tot]=P[i]-P[x],T[tot].angle=atan2(T[tot].y,T[tot].x);
//	for(i=1;i<=tot;i++)
//	{
//		k=0;
//		for(j=1;j<=tot;j++)if(T[i]*T[j]<0)k++;
//		ans=sub(ans,mul(q[k],p[2]));
//	}
	sort(T+1,T+tot+1);j=1;cnt=0;
    for(i=1;i<=tot;i++)
    {
        while ((T[i]*T[j%tot+1])>0)j=j%tot+1,cnt++;
        ans=sub(ans,mul(q[n-2-cnt],p[2]));
        if(cnt)cnt--;
        else j++;
    }
//	sort(T+1,T+tot+1);
//	for(i=1;i<=tot;i++)T[tot+i]=T[i];
//	i=tot+1;j=1;
//	while(i<=tot+tot)
//	{
//		while(j<i&&)j++;
//		ans=sub(ans,mul(q[i-j],p[2]));i++;
//	}
}
main()
{
	int i,j,k;
	scanf("%lld%lld",&n,&p[1]);
	p[0]=1;q[0]=1;q[1]=sub(1,p[1]);
	for(i=1;i<=n;i++)scanf("%lf%lf",&P[i].x,&P[i].y);
	for(i=2;i<=n;i++)p[i]=mul(p[i-1],p[1]);
	for(i=2;i<=n;i++)q[i]=mul(q[i-1],q[1]);
	ans=mul(mul(3,n),p[1]);ans=sub(ans,3);
	ans=add(ans,mul(3,q[n]));
	for(i=1;i<=n;i++)Work(i);
	ans%=mod;ans+=mod;ans%=mod;
	printf("%lld",ans);
}