土下座しながら探索中

主に競技プログラミング

AOJ 1047 : Crop Circle

問題リンク : Crop Circle | Aizu Online Judge

問題概要 :
n個の円の中心点の座標と半径が与えられる
円周上で他のどの円にも囲まれていないような部分の長さの総和を求めよ

解法 :
各円について、他の円との交点で細分化する
例えば円0については以下通りにする

円0とその他の円との交点を列挙する
円0の中心点を基準に角度でソートする ( atan2で角度を取得 )
これによって反時計回りで交点が並んでいることになる
後は、交点iと交点i+1の中心点を求めてそれが他の円に内包されていないかどうかを判定する
2つの交点の中心点はatan2で交点iの角度 + (交点iと交点i+1を反時計回りにみた時の角度 ) / 2 で求めた角度を利用して、計算すると良い
その角度をargとすると
( 円0の中心点のx座標 + cos(arg) * 円0の半径, 円0の..y座標 + sin(arg) * 円0の半径 ) が交点間の中心点となる
内包されていないのであればその長さを答えに加算する
それと、完全に他の円に内包されているものははじくこと

コード :

// ライブラリはカット
const int MAX_N = 200;
Point cp[MAX_N];
double r[MAX_N];
int n;

Point vir;
bool comp_angle(Point a,Point b) {
  Vector va = a - vir;  
  Vector vb = b - vir;
  return atan2(va.y,va.x) < atan2(vb.y,vb.x);
}

double cw_angle(Point p0,Point p1,Point p2){
  double ret = M_PI - getArg(p0,p1,p2);
  if( ccw(p1,p0,p2) == COUNTER_CLOCKWISE ) ret = 2*M_PI - ret;
  return ret;
}

bool  LT(double a,double b) { return !equals(a,b) && a < b; }
bool LTE(double a,double b) { return  equals(a,b) || a < b; }

struct Data {
  Segment seg;
  Point c;
  int index;
  bool operator < ( const Data &data ) const {
    if( seg == data.seg ) return seg < data.seg;
    if( index != data.index ) return c < data.c;
    return index < data.index;
  }
  bool operator == ( const Data &data ) const { return seg == data.seg && c == data.c; }
};

bool check(Data data){
  double arg = cw_angle(data.seg.p2,data.c,data.seg.p1);
  double left_angle = atan2(data.seg.p1.y-cp[data.index].y,data.seg.p1.x-cp[data.index].x);
  if( LT(left_angle,0.0) ) left_angle += 2*M_PI;
  double middle_angle = left_angle + arg / 2.0;
  Point mp = Point(cp[data.index].x+cos(middle_angle)*r[data.index],cp[data.index].y+sin(middle_angle)*r[data.index]);
  assert( equals(abs(cp[data.index]-mp),r[data.index]) );
  rep(i,n) if( i != data.index ) {
    double dist = abs(mp-cp[i]);
    if( LT(dist,r[i]) ) return false;
  }
  return true;
}

bool insideCC(Point a,double ra,Point b,double rb){
  double d = sqrt(norm(a-b));
  double r1 = max(ra,rb);
  double r2 = min(ra,rb);
  if(!equals(d,r1-r2) && d < r1-r2) return ra < rb; 
  return false;
}

double compute(){

  double ret = 0;  
  vector<Data> buf;
  rep(i,n) {
    vector<Point> vp;
    rep(j,n) if( i != j && intersectCC(cp[i],r[i],cp[j],r[j]) ) {
      pair<Point,Point> tmp = crosspointCC(cp[i],r[i],cp[j],r[j]);
      vp.push_back(tmp.first), vp.push_back(tmp.second);
    }
    if( vp.empty() ) { 
      bool failed = false;
      rep(j,n) if( i != j ) if( insideCC(cp[i],r[i],cp[j],r[j]) ) { failed = true; break; }
      if( !failed ) ret += M_PI * r[i] * 2;
      continue; 
    }
    sort(vp.begin(),vp.end());
    vp.erase(unique(vp.begin(),vp.end()),vp.end());
    vir = cp[i];
    sort(vp.begin(),vp.end(),comp_angle);
    rep(j,vp.size()) buf.push_back((Data){Segment(vp[j],vp[(j+1)%(int)vp.size()]),cp[i],i});
  }

  sort(buf.begin(),buf.end());
  buf.erase(unique(buf.begin(),buf.end()),buf.end());

  rep(i,buf.size()) if( check(buf[i]) ) ret += r[buf[i].index] * cw_angle(buf[i].seg.p2,buf[i].c,buf[i].seg.p1);

  
  return ret;
  
}

int main(){
  while( cin >> n, n ){
    rep(i,n) cin >> cp[i].x >> cp[i].y >> r[i];
    printf("%.10lf\n",compute());
  }
  return 0;
}