PIE - 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 floating point number with an absolute error of at most 10-3.

Example

Input:
3
3 3
4 3 3
1 24
5
10 5
1 4 2 3 4 5 6 5 4 2

Output:
25.1327
3.1416
50.2655

hide comments
mradul_2212: 2023-10-18 16:12:55

can someone explain me the predicate function used in this question....what's the logic used in finding is possible to distribute m amount of pie among all f+1 friends?

swapnamoy: 2023-07-18 15:00:06

the first on may seem wrong but it is not cause 26 something by dividing equally can come from "3" ones but as there are 4 people 2 26.something cant come from "4" one as it has 5.something radius. all the best.

kunal972: 2022-12-19 13:46:59

what is value of high?

shnatan: 2022-10-31 10:29:36

Explaining the first test case :
The number of friends is 3, so the total number of people among which the pies are to be distributed is 4.
The sizes of the pie is: 4 3 3.
So if the pies are distributed such that the size of each pie is half of the size of the first pie(i.e 4) then each person will get the maximum volume of pie.
Volume everyone will get=pi*(4*4)/2=25.1327.
This way the 2 equal halves of the first pie are made and no messy piece is made, some of the pie from the '3' and '3' pie is spoiled but that is acceptable.

kashipaka123: 2022-08-20 14:33:04

3 3
4 3 3
28.2743 its giving me the output as these instead of asked 25.dhjf but other are passing with precision of 1e-3

taejin_101: 2022-05-13 17:19:03

Few things to remember while you code this problem:
1. Use PI as 3.141592653589793238
2. Use fixed and setprecision(4)
3. Pie must be distributed among friends + 1 .
4. More than 1 piece can be gained from a single pie.

nitincp: 2022-02-16 06:06:53

testcase 1
3 3
4 3 3
areas of pies will be
50.2655 28.2743 28.2743
therefore maximum size of pie = 28.2743
ans given = 25.1327
therefore it seems wrong

chetan06: 2021-12-31 16:44:19

I don't know why I am getting wrong answer
<snip>
Can somebody explain

[NG]: Please read the footer.

Last edit: 2022-01-01 05:02:52
rajat_jadam: 2021-07-24 15:41:30

epsilon=1e-4
Fixed
setprecision(4)

Tadaaaa !

nubskr: 2021-07-10 14:24:17

Don't use the standard while loop in binary search, you can't compare doubles here


Added by:overwise
Date:2007-10-02
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:ACM ICPC NWERC 2006