链接:poj 3122

题意：我生日派对时，准备了n个圆柱形的pie,半径比一定相同，但高都为1，

邀请了f个朋友，加上自己一共f+1人，需要将n个pie分给f+1个人

要求：每个人分得的pie尺寸要一样大，

并且同一个人所分的pie要是从同一个pie上得到的，n个pie分完后可以有剩余

求：每个人最多可以分多少

分析：因为同一个人所分的pie都来自同一个pie，

若每个人所分的最大体积为a,那么比a小的pie肯定得舍弃。

将每个人最多分得的pie看成半径为r的圆柱，则最大尺寸为PI*r*r*1,

可以用二分算法，下界为0，上界为pie的最大半径

要注意精度问题

#include
  
   
#include
   
     #define PI acos(-1.0) #define eps 1e-8 int n,m; double rad[10010]; bool judge(double size) { int cnt=0; for(int i=1;i<=n;i++) cnt+=(int)(rad[i]*rad[i]/(size*size)); if(cnt>=m) return true; return false; } double bin_search(double l,double r) { double mid; while(r-l>eps){ mid=(l+r)/2; if(judge(mid)) //判断分该半径的pie是否够分 l=mid; else r=mid; } return mid; } int main() { int T; scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); m++; double r=0; for(int i=1;i<=n;i++){ scanf("%lf",&rad[i]); if(rad[i]>r) r=rad[i]; } double ansR=bin_search(0.0,r); printf("%.4lf\n",PI*ansR*ansR); } return 0; }