HDU 1969 Pie（二分法）
My birthday is coming up and traditionally I’m serving pie. Not just one pie, no, I have a number N of them, of various tastes and of various sizes. F of my friends are coming to my party and each of them gets a piece of pie. This should be one piece of one pie, not several small pieces since that looks messy. This piece can be one whole pie though. My friends are very annoying and if one of them gets a bigger piece than the others, they start complaining. Therefore all of them should get equally sized (but not necessarily equally shaped) pieces, even if this leads to some pie getting spoiled (which is better than spoiling the party). Of course, I want a piece of pie for myself too, and that piece should also be of the same size. What is the largest possible piece size all of us can get? All the pies are cylindrical in shape and they all have the same height 1, but the radii of the pies can be different.
Input
One line with a positive integer: the number of test cases. Then for each test case: • One line with two integers N and F with 1 ≤ N, F ≤ 10000: the number of pies and the number of friends. • One line with N integers ri with 1 ≤ ri ≤ 10000: the radii of the pies.
Output
For each test case, output one line with the largest possible volume V such that me and my friends can all get a pie piece of size V . The answer should be given as a oating point number with an absolute error of at most 10−3 .
Sample Input
3
3 3
4 3 3
1 24
5
10 5
1 4 2 3 4 5 6 5 4 2
Sample Output
25.1327
3.1416
50.2655
題目意思：有N個餡餅，要分給F+1個人。要求每個人分到的面積相同，求最大的面積是多少！（分的要求，每個人手上只能有一個餡餅.....餡餅可以分割）
解題思路：1.題目的最終目的不外乎就是確定 一個最大的面積值。這個面積值得范圍是0至所有餡餅面積之和sum...然後再想想，它要分給F+1個人，那麼它的范圍又縮小到了
0至sum/(F+1)。
2.然後就想辦法二分縮小范圍，直到確定最大面積值。通過來判斷分的實際個數t與F+1比較來二分。如果t>=F+1，說明要求的值在右邊，否則在左邊。（注意要有等於，不然輸出相差太大）
3。輸出
代碼如下：
1 #include <stdio.h>
2 #include <math.h>
3 int a[10000],N,F;
4 double pi=acos(-1.0);
5 double r,l,mid,sum=0,V;
6 bool judge(double x)
7 {
8 int t=0;
9 double V1;
10 for(int i=0;i<N;i++){
11 V1=a[i]*a[i]*pi;
12 //t+=int(V1/x);
13 if(V1>=x) t+=int(V1/x);
14 }
15 //printf("t=%d\n",t);
16 if(t>=F+1) return false;
17 else return true;
18 }
19 void zhao()
20 {
21 r=sum/(F+1);
22 l=0;
23 while(r-l>0.0001){
24 mid=(r+l)/2;
25 //printf("r=%lf\n",r);
26 //printf("l=%lf\n",l);
27 //printf("mid=%lf\n",mid);
28 if(judge(mid)){
29 //printf("1\n");
30 r=mid;
31 }
32 else{
33 //printf("0\n");
34 l=mid;
35 }
36 }
37 printf("%.4lf\n",r);
38 }
39 int main()
40 {
41 int T;
42 scanf("%d",&T);
43 while(T--){
44 scanf("%d%d",&N,&F);
45 for(int i=0;i<N;i++){
46 scanf("%d",&a[i]);
47 V=a[i]*a[i]*pi;
48 sum+=V;
49 }
50 //printf("r=%lf\n",sum);
51 zhao();
52 //printf("\n*************************\n");
53 }
54 }
