Codeforces 62 C. Inquisition

問題

n個の三角形が与えられる。
それらの和集合からなる図形の周長を求めよ。

制約条件

n≦100
0＜座標＜10^5

方針

それぞれの辺を、他の辺との交点で区切る。
その区間ごとに、それが周であるか（他の図形の内部にない）を判定し、
周であったならば周長にその区間の長さを足す。

ソースコード

double cp(const L &l, const L &m) {
  double A = cross(l[1] - l[0], m[1] - m[0]);
  double B = cross(l[1] - l[0], l[1] - m[0]);
  return B / A;
}

int n;
P p[100][3];
void run(){
  cin>>n;
  rep(i,n)rep(j,3)cin>>p[i][j].real()>>p[i][j].imag();
  double ans=0;
  
  rep(i,n)rep(j,3){
    vector<double> c;
    rep(k,n)rep(l,3)if(i!=k){
      if(intersectSS(L(p[i][j],p[i][(j+1)%3]),L(p[k][l],p[k][(l+1)%3])))
        c.pb(cp(L(p[k][l],p[k][(l+1)%3]),L(p[i][j],p[i][(j+1)%3])));
    }
    c.pb(0); c.pb(1);
    sort(all(c));
    
    rep(k,c.size()-1){
      P m=p[i][j]+(p[i][(j+1)%3]-p[i][j])*((c[k+1]+c[k])/2);
      bool ok=1;
      rep(a,n)if(a!=i){
        bool pl=1,mi=1;
        rep(b,3){
          double t=cross(p[a][b]-m,p[a][(b+1)%3]-m);
          if(t<=0)pl=0;
          if(t>=0)mi=0;
        }
        if(pl||mi){
          ok=0; break;
        }
      }
      if(ok){
        ans+=abs(p[i][(j+1)%3]-p[i][j])*(c[k+1]-c[k]);
      }
    }
  }
  printf("%.9f\n",ans);
}