首页 > 代码库 > 【bzoj1913】 Apio2010—signaling 信号覆盖

【bzoj1913】 Apio2010—signaling 信号覆盖

http://www.lydsy.com/JudgeOnline/problem.php?id=1913 (题目链接)

题意

  给出一个平面上n个点,求任选3个点画一个圆所包含的点的期望值。

Solution

  这个问题可以转化为凹凸多边形的问题求解(当然我是没想到的)。。左转题解:http://blog.csdn.net/regina8023/article/details/45556321

细节

  注意存放极角的数组要开成2倍。

代码

// bzoj1913#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#include<queue>#define LL long long#define inf 2147483640#define eps 1e-6#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;const int maxn=2000;struct point {int x,y;}p[maxn];LL C[maxn][maxn];double a[maxn<<1];int n;int main() {	scanf("%d",&n);	for (int i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y);	for (int i=0;i<=n;i++) C[i][0]=1;	for (int i=1;i<=n;i++)		for (int j=1;j<=i;j++) C[i][j]=C[i-1][j]+C[i-1][j-1];	LL t2,t1=0;	for (int i=1;i<=n;i++) {		int cnt=0;		for (int j=1;j<=n;j++) if (i!=j) {				a[++cnt]=atan2(p[j].y-p[i].y,p[j].x-p[i].x);				if (a[cnt]<0) a[cnt]+=2*Pi;			}		sort(a+1,a+cnt+1);		for (int j=1;j<=cnt;j++) a[j+cnt]=a[j]+2*Pi;		for (int j=1,k=1;j<=cnt;j++) {			while (a[k+1]-a[j]<Pi && k<2*cnt) k++;			t1-=C[k-j][2];   //凸多边形个数		}		t1+=C[n-1][3];	}	t2=C[n][4]-t1;	printf("%.6lf",(double)(t1+t2*2)/C[n][3]+3);	return 0;}

  

【bzoj1913】 Apio2010—signaling 信号覆盖