bzoj1043: [HAOI2008]下落的圆盘

时间:2022-05-15 00:54:01

这道题题目很短,看一下数据范围n<1000,直接枚举圆盘。

对于圆盘i,枚举它上面的圆盘,计算圆盘i被它们覆盖的弧的起始位置与终止位置,然后线段覆盖可得圆盘i被覆盖的周长,就可得答案。

注意圆外离与内含的情况。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define pi 3.1415926535897932384626433832795
using namespace std;
struct circle{double r,x,y;}a[10000];
struct arc{double a,b;}q[10000];
int n,le;double Ans;
double di(circle a,circle b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double ang(double R,double d,double r)
{
	return acos((R*R+d*d-r*r)/(2*R*d));
}
bool cmp(arc a,arc b)
{
	if (a.a==b.a)return a.b<b.b;
	else return a.a<b.a;
}
void add(double l,double r)
{
	q[++le].a=l,q[le].b=r;
}
int main()
{
	freopen("disc.in","r",stdin);
	freopen("disc.out","w",stdout);
	
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		scanf("%lf%lf%lf",&a[i].r,&a[i].x,&a[i].y);
	for (int i=1;i<=n;i++)
	{
		bool f=0;le=0;
		for (int j=i+1;j<=n;j++)
		{
			double dis=di(a[i],a[j]);
			if (dis<=a[j].r-a[i].r) {f=1;break;}
			if (dis>=a[i].r+a[j].r||dis<=a[i].r-a[j].r)
				continue;
			double x=a[j].x-a[i].x,y=a[j].y-a[i].y;
			double a1=atan2(x,y)+pi;
			double a2=ang(a[i].r,dis,a[j].r);
			if (a1-a2<0)    add(0,a1+a2),   add(a1-a2+2*pi,2*pi);else
			if (a1+a2>2*pi) add(a1-a2,pi*2),add(0,a1+a2-2*pi);
			else add(a1-a2,a1+a2);
		}
		if (f==1)continue;
		sort(q+1,q+le+1,cmp);
		double l=-1,r=-1,sum=0;
		for (int j=1;j<=le;j++)
		if (q[j].a<=r)
			r=max(r,q[j].b);
		else
		{ sum+=r-l; l=q[j].a; r=q[j].b; }
		sum+=r-l;
		Ans+=(2*pi-sum)*a[i].r;
	}
	printf("%.3f\n",Ans);
	return 0;
}