BZOJ 1043 [HAOI2008]下落的圆盘

#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;}elseans+=2*pi*a[i].r;}printf("%.3f\n",ans);return 0;
}