bzoj 1913: [Apio2010]signaling 信号覆盖【旋转卡壳(?)】

参考：https://blog.csdn.net/qpswwww/article/details/45334033 讲的很清楚

做法比较像旋转卡壳但是具体是不是我也不清楚..

首先知道只要求出每种方案在圆上和圆中的和就可以。

注意到题目中有一个限制：“保证任何三个房子都不在同一条直线上，任何四个房子都不在同一个圆上。”，所以考虑构成圆的三个点和需要判断的第四个点组成的四边形：

对于凹四边形，只有一种情况，第四个点一定在圆内；

对于凸四边形，第四个点可能在园中，圆上，圆外，其中园中，圆上是符合条件的。

又，总的四边形个数是\( C_n^4 \)，所以只求得凸四边形的个数即可。

把凸四边形看做一个三角形中有一个点，现在需要找出没有覆盖这个点的三角形，枚举中间这个点，然后把其他点按这个点极角排序，枚举三角形上的一个点，用旋转卡壳一样的东西取卡另外两个点的可选区间，然后用\( C_{n-1}^3 \)减去这个数加进ans里即可。

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

using namespace std;

const int N=3005;

int n;

long long ans;

double p[N];

struct dian

{

	double x,y;

	dian(double X=0,double Y=0)

	{

		x=X,y=Y;

	}

	dian operator - (const dian &a) const

	{

		return dian(x-a.x,y-a.y);

	}

}a[N];

long long C(long long n,long long m)

{

	long long r=1ll,c=1ll;

	for(int i=0;i<m;i++)

		r*=(n-i);

	for(int i=1;i<=m;i++)

		c*=i;

	return r/c;

}

void wk(int x)

{

	int top=0;

	for(int i=1;i<=n;i++)

		if(i!=x)

			p[++top]=atan2((a[i]-a[x]).y,(a[i]-a[x]).x);

	sort(p+1,p+1+top);

	long long con=0;

	for(int i=1;i<n;i++)

		p[++top]=p[i]+2*M_PI;

	int w=1;

	for(int i=1;i<n;i++)

	{

		w=max(w,i+1);

		while(w<=top&&p[w]<p[i]+M_PI)

			w++;

		if(w-i-1>=2)

			con+=C(w-i-1,2);

	}

	ans+=C(n-1,3)-con;

}

int main()

{

	scanf("%d",&n);

	if(n<=3)

	{

		puts("0");

		return 0;

	}

	for(int i=1;i<=n;i++)

		scanf("%lf%lf",&a[i].x,&a[i].y);

	for(int i=1;i<=n;i++)

		wk(i);

	printf("%lf\n",(double)(ans+2*(C(n,4)-ans))/(double)C(n,3)+3.0);

	return 0;

}

巴特西

bzoj 1913: [Apio2010]signaling 信号覆盖【旋转卡壳(?)】

最新文章

热门文章