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)); } }