hdu 1969 Pie（二分）
题意：有n块高为1的圆柱形蛋糕，f+1个人，每块给出半径ri。现给每个人分一块蛋糕（可由分割得），要求面积相等。求每个人分得的最大体积。
思路：进一步了解题意，就是每个人都必须有且仅有一块蛋糕，且每个人得到蛋糕的体积相等。
令ave = 蛋糕总体积 / （f+1），理想状态下，体积为ave，即最大为ave。
所以从0~ave进行二分，查找出最佳的答案。
PS： 1、#define PI (double)acos(-1.0) （卡精度，nWA）
2、int num = 0;
for(int i=1; i<=n; i++)
{
num += (int)(pie[i]/m);
}
if(num<f) r = m;
else l = m;
由于 (int)(pie[i]/m)是丢弃尾数，所以一定是num<f : r = m; num >=f : l = m.
1 #include <cstdio>
2 #include <cstring>
3 #include <cmath>
4 #define N 10005
5 #define PI (double)acos(-1.0)
6 double pie[N];
7 int main()
8 {
9 int t,n;
10 double f;
11 scanf("%d",&t);
12 while(t--)
13 {
14 double ave = 0;
15 scanf("%d%lf",&n,&f);
16 f = f + 1;
17 for(int i=1; i<=n; i++)
18 {
19 scanf("%lf",&pie[i]);
20 pie[i] = pie[i] * pie[i];
21 ave += pie[i];
22 }
23 ave /= f;
24 double l = 0, r = ave, m;
25 while(fabs(r-l)>1e-8)
26 {
27 m = (l + r) / 2;
28 int num = 0;
29 for(int i=1; i<=n; i++)
30 {
31 num += (int)(pie[i]/m);
32 }
33 if(num<f) r = m;
34 else l = m;
35 }
36 printf("%.4lf ",m*PI);
37 }
38 return 0;
39 }
2 #include <cstring>
3 #include <cmath>
4 #define N 10005
5 #define PI (double)acos(-1.0)
6 double pie[N];
7 int main()
8 {
9 int t,n;
10 double f;
11 scanf("%d",&t);
12 while(t--)
13 {
14 double ave = 0;
15 scanf("%d%lf",&n,&f);
16 f = f + 1;
17 for(int i=1; i<=n; i++)
18 {
19 scanf("%lf",&pie[i]);
20 pie[i] = pie[i] * pie[i];
21 ave += pie[i];
22 }
23 ave /= f;
24 double l = 0, r = ave, m;
25 while(fabs(r-l)>1e-8)
26 {
27 m = (l + r) / 2;
28 int num = 0;
29 for(int i=1; i<=n; i++)
30 {
31 num += (int)(pie[i]/m);
32 }
33 if(num<f) r = m;
34 else l = m;
35 }
36 printf("%.4lf ",m*PI);
37 }
38 return 0;
39 }