【BZOJ1043】[HAOI2008]下落的圆盘

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

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

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

#include <cstdio>#include <iostream>#include <cstring>#include <cmath>#include <algorithm>#define pi acos(-1.0)using namespace std;struct circle{	double x,y,r;	circle(){}	circle(double a,double b)	{x=a,y=b;}	circle operator + (circle a)	{return circle(x+a.x,y+a.y);}	circle operator - (circle a)	{return circle(x-a.x,y-a.y);}	circle operator * (double a)	{return circle(x*a,y*a);}	circle operator / (double a)	{return circle(x/a,y/a);}}c[1010];struct node{	double x;	int v;}p[2010];double ans;double dist(circle a,circle b)	{return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}int n,tot,sum,flag;bool cmp(node a,node b){	return a.x<b.x;}int main(){	scanf("%d",&n);	int i,j;	for(i=1;i<=n;i++)	scanf("%lf%lf%lf",&c[i].r,&c[i].x,&c[i].y);	for(i=1;i<=n;i++)	{		tot=sum=flag=0;		for(j=i+1;j<=n;j++)		{			double dis=dist(c[i],c[j]);			if(dis<=c[j].r-c[i].r)			{				flag=1;				break;			}			if(dis>fabs(c[i].r-c[j].r)&&dis<=c[i].r+c[j].r)			{				double a=acos((c[i].r*c[i].r+dis*dis-c[j].r*c[j].r)/(2*c[i].r*dis));				double b=atan2(c[j].y-c[i].y,c[j].x-c[i].x);				p[++tot].x=b-a,p[tot].v=1,p[++tot].x=b+a,p[tot].v=-1;				if(p[tot-1].x<0)	p[tot-1].x+=2*pi;				if(p[tot].x<0)	p[tot].x+=2*pi;				if(p[tot-1].x>=2*pi)	p[tot-1].x-=2*pi;				if(p[tot].x>=2*pi)	p[tot].x-=2*pi;				if(p[tot-1].x>p[tot].x)	sum++;			}		}		if(flag)	continue;		ans+=c[i].r*2*pi;		if(!tot)	continue;		sort(p+1,p+tot+1,cmp);		for(j=1;j<=tot;j++)		{			if(sum)	ans-=c[i].r*(p[j].x-p[j-1].x);			sum+=p[j].v;		}		if(sum)	ans-=c[i].r*(2*pi-p[tot].x);	}	printf("%.3lf",ans);	return 0;}