bzoj1043[HAOI2008]下落的圆盘 计算几何

1043: [HAOI2008]下落的圆盘

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 1598  Solved: 676
[Submit][Status][Discuss]

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

 

Source

可以考虑后放的盘子对先放的盘子造成的覆盖影响
枚举每个盘，这个盘贡献的答案就是它的周长减去被后面的盘所覆盖的部分
圆和圆相交部分长度可以转化成线段覆盖问题来计算：算出中轴线的角度x，再计算圆心到2交点的角度y，

圆上被覆盖的弧度区间就是[x-y,x+y]
几个圆与这个圆相交，把相交覆盖的弧转化成圆上的线段，做一个线段覆盖问题就可以解决

 #include<bits/stdc++.h>

 #define reg register

 #define N 1005

 using namespace std;

 int n,tp;double x[N],y[N],r[N],ans;const double pi=acos(-);struct node{double l,r;}q[N<<];

 double dis(int i,int j){return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));}

 bool con(int i,int j){return r[i]>=r[j]+dis(i,j);}

 bool cmp(node a,node b){return a.l<b.l;}

 void push(int i,int j){

     double d,k,t,mv;

     d=dis(i,j);k=atan2(y[j]-y[i],x[j]-x[i]);

     t=(d*d+r[i]*r[i]-r[j]*r[j])//d;

     mv=acos(t/r[i]);

     q[++tp]=(node){k-mv,k+mv};

 }

 double calc(int p){

     tp=;

     for(reg int i=p+;i<=n;i++)

     if(con(i,p))return ;

     for(int i=p+;i<=n;i++){

         if(con(p,i)||dis(i,p)>r[i]+r[p])continue;

         push(p,i);

     }

     for(reg int i=;i<=tp;i++){

         if(q[i].l<)q[i].l+=*pi;

         if(q[i].r<)q[i].r+=*pi;

         if(q[i].l>q[i].r){

             q[++tp]=(node){,q[i].r};

             q[i].r=*pi;

         }

     }

     sort(q+,q++tp,cmp);

     double cov=,mx=q[].l;

     for(reg int i=;i<=tp;i++){

         mx=max(mx,q[i].l);

         if(q[i].r<=mx)continue;

         cov+=q[i].r-mx;mx=q[i].r;

     }

     double ret=r[p]*(*pi-cov);

     return ret;

 }

 int main(){

     scanf("%d",&n);

     for(reg int i=;i<=n;i++)

     scanf("%lf%lf%lf",&r[i],&x[i],&y[i]);

     for(reg int i=;i<=n;i++)ans+=calc(i);

     printf("%.3lf\n",ans);

     return ;

 }