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

      （1）编程思路。

      题目要求是公平地分披萨Pie。

      每个pie都是高为1的圆柱体，输入这n个pie的每一个尺寸（半径），如果要公平地把pie分给每一个人（就是所有人得到的pie尺寸一致，但是形状可以不同），而且每个人得到的那份pie必须是从同一个pie上得到的。注意，由于每个人只能从一个pie上分，因此公平分Pie，不是简单求个平均值，而是要寻找到平均值的最大值。

      例如，有3个pie, 尺寸分别为1,2,3。

      如果要给每人尺寸为2的pie，那么最多分给2个人，而不是3个人。因为第一个pie尺寸为1，小于2，扔掉；第二个pie尺寸为2，等于2，刚好分给一个人；第三个pie尺寸为3，切出尺寸为2的一份，分给一个人，剩下的尺寸为1的就扔掉。注意：第1个pie和第3个pie剩余的合起来好像正好可以分给1人，但不能这样做。如果这样做，就变成单纯地求平均值了。

      同样采用二分法解决这个最大化平均值问题。

      令下界left=0，即每人都分不到pie，上界right=Sum/(f+1)，即每人都得到了算术平均值，实际上难做到，只可能在n个人分n个pie，每个pie还等大时出现。

       使用二分法得到mid，计算“如果按照mid的尺寸分pie，能分给多少人”。如果当前mid值可以将pie分给f+1个人，则增大下界，使left=mid；如果按mid值分不了f+1人，则mid取大了，减小上界，使right=mid；.然后最终使left 与right无限逼近答案。注意：程序中可以使用 while ((right-left)>1e-6)作为循环控制条件。

      （2）源程序。

#include <stdio.h>

#include <math.h>

const double PI = 3.1415926535898;

double pie[100010];

int n,f;

bool judge(double x)

{

         int num = 0,i;

         for (i = 0; i < n; i++)

                   num += (int)(pie[i] / x);

         return num >= f;

}

int main()

{

    int t,r;

    double sum,left,right,mid;

    scanf("%d",&t);

    while(t--)

    {

        sum=0;

        scanf("%d %d",&n,&f);

        f++;

        for(int i = 0 ; i < n ; i++)

        {

            scanf("%d",&r);

            pie[i]=r*r*PI;

            sum+=pie[i];

        }

        left=0.0;

        right=sum/f;

        while (fabs(right-left)>1e-6)

        {

            mid=(left+right)/2;

            if (judge(mid))

            {

                left=mid;

            }

            else

            {

                right=mid;