Description

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 ≤ 10 000: the number of pies and the number of friends.
• One line with N integers ri with 1 ≤ ri ≤ 10 000: 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 floating point number with an absolute error of at most 10

⁻³.

Sample Input

33 34 3 31 24510 51 4 2 3 4 5 6 5 4 2

Sample Output

25.13273.141650.2655

题意是：某人在生日的时候请朋友一起吃pie，但是他的朋友十分挑剔，如果有人分到了一块比其他人大的pie，那么其他的朋友就会抱怨，因此每个人包括主人在内，都必须分到大小一样的pie，但是每个人的pie只能是从一块大的圆形pie中切出来的，也就是每个人得到的必须是一个完整的，不一定要是圆形，但不能是几块拼在一起，要求求出每人能分到的最大pie的面积。

先给出测试案例的个数，给定圆形pie的数量N，朋友数量F，以及每个pie的半径r。 利用二分求其中体积最大的那个pie，上界是面积最大的那块pie的面积，下界为0。求出mid看看以此大小可以分给多少人，如果人数小于F则是mid大了，high=mid，如果人数>=F则满足要求，求出最大的的即可。

pie是圆柱状，高是1，我们不用管。

#include 
    
     #include 
     
      #include 
      
       using namespace std;#define PI 4.0*atan(1.0) //因为是高精度所以圆周率PI用库函数来求int N,F;double s[10000];  //存储N块pie的面积bool isok(double area) //看看这个面积去分，人数够不够{
        int sum=0,i;    for(i=0;i
       
        =F)        return true;    else        return false;}int main(){
        int T;    cin>>T;    while(T--)    {
            int radiu,i;        double maxn=0;        cin>>N>>F;        F++;    //因为主人也要吃，所以F要加1        for(i=0;i
        
         >radiu;   //输入半径            s[i]=double(radiu*radiu*PI); //当即计算出此pie的面积            if(s[i]>maxn)                maxn=s[i];  //找出面积最大的pie        }        double low=0,height=maxn; //下界为0，上界是最大的pie的面积        while(height-low>=1e-4)  //体重说误差不能>10−3, 我们用精度10−4
        
       
      
     
    

{
                 double mid=(low+height)/2;            if(isok(mid))                 low=mid;            else                height=mid;        }        cout<
    
     <