uva-12097-Pie

/*將pie平均分給F+1個人，pie若太小可以不考慮分配出去，不可以將幾個pie的碎屑合成一塊，請問最大面積。使用二元搜尋考慮各種面積的可能性，使用函式決定該面積是否可行。 */ #include <iostream>#include <cmath>#include <algorithm>using namespace std; const double PI=acos(-1.0); double r[10010]; int n,f; bool bs(double x){//true表示可以分給f+1個人 int cnt=0; for(int i=0;i<n;i++){ cnt+=(int)(r[i]/x); } return (cnt > f);//自己也要一塊 } int main(){ int t; double L,R,M,m; cin >> t; while(t--){ cin >> n >> f; m=0; for(int i=0;i<n;i++) { cin >> r[i]; r[i]=r[i]*r[i]; m=max(m,r[i]); } L=0.0; R=m; while(R-L>0.00001){//二分搜尋 M=(L+R)/2; if(bs(M)) L=M; else R=M; } cout.precision(4); cout << fixed << PI*L <<endl; } }