PKU 3122 Pie
http://poj.org/problem?id=3122
n個のパイがあり、それぞれr_iの半径を持っている。
これをf人の友人とそして自分で同じ大きさにきって分け合いたい。
切れ端は捨てることにするとき、最大でどのくらいのサイズで分け合うことができるかを求めるという問題。
大きさに関して二分探索。よくわからないWAをだした。
ll ra[10000]; main(){ int test; cin>>test; while(test--){ int n,f; cin>>n>>f; ++f; rep(i,n)cin>>ra[i]; double l=0,u=1LL<<54; while(abs(u-l)>0.00001){ double mid=(l+u)/2; int t=f; rep(i,n){ int k=floor(pi*ra[i]*ra[i]/mid); t-=k; } if(t>0)u=mid; else l=mid; } printf("%.4f\n",l); } }