AOJ : 1213 - Heavenly Jewels

問題概要

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1213
(0,0)〜(10000,10000)の土地のどこかに宝石が落ちてきます.
この土地には, ICさんとPCさんとACMさんの3人の人が住んでいます(それぞれの人の家の座標は与えられる).
宝石を取ることができるのは, 宝石と家が一番近い人です. ただし, 近い人が複数いる場合は, ICさんが優先的にとることができます.
土地の全ての位置に等確率で宝石が落ちてくるならば, ICさんが宝石を取れる確率はいくらでしょうか.

アルゴリズム

↓この図を見ていただければ.

つまり, 「水色の面積 / 全体の面積」が答えになります.

プログラム

typedef complex<double> P;

//多角形を直線で切断する
vector<P> convex_cut(const vector<P> &p,P a,P b){...}

//多角形の面積を求める
double area(vector<P> &p){...}

//aとbからの等距離の点を, med以外で求める
P getPoint(P a,P b,P med){
  P ab = b - a;
  P n1 = (ab * P(0,1)) / abs(ab);
  double mul = 0.1;
  return med + n1 * mul;
}

int main(){
  P t[3];

  for(int SET=1;;SET++){
    rep(i,3){
      cin>>t[i].real()>>t[i].imag();
    }
    if(t[0].real() == 0) break;

    //初期の正方形
    vector<P> v;
    v.push_back(P(0,0));
    v.push_back(P(10000,0));
    v.push_back(P(10000,10000));
    v.push_back(P(0,10000));

    //ICとPC, ICとACM, の関係で多角形を切断
    rep(i,2){
      double div = 2;
      P med = (t[0] + t[i+1]) / div;
      P med_left = getPoint(t[0],t[i+1],med);
      if(ccw(med_left,med,t[0]) == 1){
        v = convex_cut(v,med_left,med);
      }
      else{
        v = convex_cut(v,med,med_left);
      }
    }

    printf("%d %.5f\n",SET,area(v)/(10000*10000));
  }
}