1213 - Heavenly Jewels

AOJ

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1213

問題

10000×10000の島があり、IC、PC、ACMが住んでいる。
この島では毎日、空から任意の場所に宝石が落ちてきて、この宝石が落ちた場所に最も近いところに住んでいる人が宝石を得ることが出来る。
IC、PC、ACMの家の座標が与えられるので、ICが宝石を得られる確率を求めよ。

解法

ICが宝石を取ることができる領域は、ICのボロノイ領域となる。
よって、ICが宝石を得る確率は、ICのボロノイ領域の面積を10000*10000で割った値となる。
宝石が複数の家から同じ距離のとき誰が得るかの優先順位が与えられているが、宝石が整数座標とは限らない任意の場所に落ちるので、無限に小さな差であり考える必要はない。

ボロノイ領域の求め方については次の記事に書くことにする。

ソース

ライブラリ等省略。
convex_cutはSpaghettiSourceのもの（を修正したもの）。

double area(const G& g) {
  double A = 0;
  for (int i = 0; i < g.size(); ++i) {
    A += cross(g[i], g[(i+1)%g.size()]);
  }
  return A/2;
}

L bisector(P a, P b) { // 垂直二等分線
  P A = (a+b)*P(0.5,0);
  return L(A, A+(b-a)*P(0, PI/2));
}

int main() {
  int ax,ay,bx,by,cx,cy;
  int nn = 0;
  while(cin>>ax>>ay>>bx>>by>>cx>>cy,ax) {
    P p1(ax,ay),p2(bx,by),p3(cx,cy);

    G g;
    g.push_back(P(0,0));
    g.push_back(P(10000,0));
    g.push_back(P(10000,10000));
    g.push_back(P(0,10000));
    
    g = convex_cut(g, bisector(p1,p2));
    g = convex_cut(g, bisector(p1,p3));
    
    printf("%d %.6f\n",++nn,area(g) / (10000*10000));
  }
}