Problem 1047 : Crop Circle

問題概要

日本語なので本文参照
（http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1047）

解法

幾何+区間を覆う長さ問題。
一つの円について、他の円1,2…によって隠される部分を[a1,b1],[a2,b2]...とすれば、
（ただしai,biは偏角とする）
区間の全ての和集合が隠される部分全体で、これは数直線上に区間が沢山あったとき、和集合の長さを求める問題そのものである。

二円の交点が求まったとき、aiに微小な量を足して、弧がどちら側にあるのかを判定している。
（a+epsが隠れているなら[a,b]が隠れる区間で、a+epsが隠れていないなら、
[-PI,a]と[b,PI]が隠れる区間になる）
このepsは1e-9だとWAで、1e-5にしたら通った。

二円の交点はがんばって求める。

ソースコード

int n;
P c[100]; double r[100];

pair<double,double> crossptCC(P a,double r,P b,double s){
  double d=abs(a-b),e=(d*d+r*r-s*s)/2/d,h=sqrt(r*r-e*e);
  P dir=(b-a)*(1/d),x=dir*e+dir*P(0,1)*h,y=dir*e-dir*P(0,1)*h;
  
  return mp(arg(x),arg(y));
}
int main(){
  while(scanf("%d",&n),n){
    rep(i,n)scanf("%lf%lf%lf",&c[i].real(),&c[i].imag(),r+i);
    double ans=0;
    rep(i,n){
      map<double,int> M;
      int cnt=0; double p,s=0;
      M[-PI]=0; M[PI]=0;
      
      rep(j,n)if(i!=j){
        double d=abs(c[i]-c[j]);
        if(d>r[i]+r[j]-EPS)continue;
        if(d<abs(r[i]-r[j])+EPS){
          if(r[i]>r[j])continue;
          goto END;
        }
        pair<double,double> crs=crossptCC(c[i],r[i],c[j],r[j]);
        double a=crs.first,b=crs.second;
        if(a>b)swap(a,b);
        if(abs(c[i]+r[i]*P(cos(a+1e-5),sin(a+1e-5))-c[j])<r[j]+EPS)M[a]++,M[b]--;
        else{
          M[-PI]++; M[a]--; M[b]++; M[PI]--;
        }
      }
      fr(j,M){
        if(cnt>0)s+=j->first-p;
        cnt+=j->second;
        p=j->first;
      }
      ans+=(2*PI-s)*r[i];
      END:;
    }
    printf("%.9f\n",ans);
  }
  return 0;
}