bzoj 1043: [HAOI2008]下落的圆盘

Description

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

Input

n ri xi y1 ... rn xn yn

Output

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

Sample Input

2
1 0 0
1 1 0

Sample Output

10.472

HINT

数据规模

n<=1000

因为n只有1000.所以对于每个圆。处理其后面落下来的环覆盖的部分，然后求和即可。

反三角函数 atan2(y,x)

#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
double pi=3.141592653;
struct circle
{
     double r;
     double x,y;
}a[1001];
struct cover
{
     double se,ee;
}b[10001];
inline bool cmp(cover x,cover y)
{
     if(x.se<y.se)
          return true;
     if(x.se==y.se&&x.ee<y.ee)
          return true;
     return false;
}
int main()
{
     int n;
     scanf("%d",&n);
     int i,j,k;
     for(i=1;i<=n;i++)
          scanf("%lf%lf%lf",&a[i].r,&a[i].x,&a[i].y);
     double ans=0;
     for(i=1;i<=n;i++)
     {
     	  int p=0;
          for(j=i+1;j<=n;j++)
          {
               double dis=(a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y);
               if(dis==0)
               {
               	    if(a[i].r<a[j].r)
                    {
					     p++;
                         b[p].se=0;
                         b[p].ee=double(2)*pi;
                         break;
                    }
                    else
                         continue;
               }
               if(dis>(a[i].r+a[j].r)*(a[i].r+a[j].r))
                    continue;
               if(dis<(a[i].r-a[j].r)*(a[i].r-a[j].r))
               {
               	    if(a[i].r<a[j].r)
                    {
					     p++;
                         b[p].se=0;
                         b[p].ee=double(2)*pi;
                         break;
                    }
                    else
                         continue;
               }
               double dx=a[j].x-a[i].x,dy=a[j].y-a[i].y;
               double de=atan2(dy,dx);
               if(de<0)
                    de=double(2)*pi+de;
               double dre=acos((a[i].r*a[i].r+dis-a[j].r*a[j].r)/(double(2)*a[i].r*sqrt(dis)));
               p++;
               b[p].se=de-dre;
               b[p].ee=de+dre;
               if(b[p].se<0&&b[p].ee<0)
               {
                    b[p].se=double(2)*pi+b[p].se;
                    b[p].ee=double(2)*pi+b[p].ee;
               }
               else if(b[p].se<0)
               {
                    double tse=b[p].se,tee=b[p].ee;
                    b[p].se=double(2)*pi+b[p].se;
                    b[p].ee=double(2)*pi;
                    p++;
                    b[p].se=0;
                    b[p].ee=tee;
               }
               else if(b[p].se>double(2)*pi&&b[p].ee>double(2)*pi)
               {
                    b[p].se-=double(2)*pi;
                    b[p].ee-=double(2)*pi;
               }
               else if(b[p].ee>double(2)*pi)
               {
                    double tse=b[p].se,tee=b[p].ee;
                    b[p].se=tse;
                    b[p].ee=double(2)*pi;
                    p++;
                    b[p].se=0;
                    b[p].ee=tee-double(2)*pi;
               }
          }
          sort(b+1,b+1+p,cmp);
          double len=0;
          for(j=1;j<=p;j++)
          {
          	   double l=b[j].se,r=b[j].ee;
               for(k=j+1;k<=p;k++)
               {
                    if(b[k].se>r)
                         break;
                    if(b[k].ee>r)
                         r=b[k].ee;
               }
               len+=(r-l);
               j=k-1;
          }
          ans+=(double(2)*pi-len)*a[i].r;
          //printf("%lf\n",len);
     }
     printf("%.3lf\n",ans);
     return 0;
}