BZOJ 1043 [HAOI2008]下落的圆盘

Description

　　有n个圆盘从天而降，后面落下的可以盖住前面的。求最后形成的封闭区域的周长。看下面这副图, 所有的红
色线条的总长度即为所求. 

Input

　　第一行为1个整数n,N<=1000
接下来n行每行3个实数,ri,xi,yi,表示下落时第i个圆盘的半径和圆心坐标.

Output

　　最后的周长，保留三位小数

Sample Input

2
1 0 0
1 1 0

Sample Output

10.472

HINT

求出每个圆被覆盖的弧度值，和圆心连线与x轴的夹角，把他当做区间，求线段覆盖。

#include<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=1005;
const double pi=acos(-1);
int n;
double ans;
struct node
{
	double x;
	int tag;
};
vector<node>ang;
struct cir
{
	double r,x,y;
	bool flg;
}a[N];
double dis(int i,int j)
{
	return sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y));
}
bool cmp(node c,node d)
{
	return c.x<d.x;
}
//以水平线为0,逆时针 
int main()
{
	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++)
	{
		ang.clear();
		for(int j=i+1;j<=n;j++)
		{
			double d=dis(i,j);
			if(d+a[i].r<=a[j].r)//完全覆盖 
			{
				a[i].flg=1;
				break;
			}
			if(a[i].r+a[j].r<=d)//相离 
				continue;
			double p=acos((a[i].r*a[i].r+d*d-a[j].r*a[j].r)/(2*d*a[i].r));//余弦定理两个圆的连线与一个圆与交点的夹角 
			double q=atan2(a[j].y-a[i].y,a[j].x-a[i].x);
			if(q<0)
				q+=2*pi;
			double tl=q-p,tr=q+p;
			if(tl>=0&&tl<=2*pi&&tr>=0&&tr<=2*pi)
				ang.push_back((node){tl,1}),ang.push_back((node){tr,-1});
			if(tl<0&&tr>=0&&tr<=2*pi)
				ang.push_back((node){2*pi+tl,1}),ang.push_back((node){2*pi,-1}),ang.push_back((node){0,1}),ang.push_back((node){tr,-1});
			if(tl>=0&&tl<=2*pi&&tr>2*pi)
				ang.push_back((node){tl,1}),ang.push_back((node){2*pi,-1}),ang.push_back((node){0,1}),ang.push_back((node){tr-2*pi,-1});
		}
		if(a[i].flg)
			continue;
		if(!ang.empty())
		{
			sort(ang.begin(),ang.end(),cmp);
			int cnt=1;
			double lst=ang[0].x,res=0;
			for(int j=1;j<ang.size();j++)
			{
				if(cnt>0)
					res+=ang[j].x-lst;
				lst=ang[j].x;
				cnt+=ang[j].tag;
			}
			ans+=(2*pi-res)*a[i].r;
		}
		else
			ans+=2*pi*a[i].r;
	}
	printf("%.3f\n",ans);
	return 0;
}