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
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

sponge26: 2021-06-09 13:26:13

USE LONG DOUBLE AND SET PRECISION TO DISPLAY UPTO 4 PLACES.
CHECK THAT TEST CASES MATCH EXACTLY ELSE YOU LL GET A WA

cryp_bipul17: 2021-04-20 16:27:31

I am applying binary search on the area possible and finding the total pieces possible from it but it is giving WA


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