IITKWPCD - Partition the sticks

You are given a set of N sticks and are required to partition them into groups of exactly 3 sticks each. While doing so, you can leave out any number of sticks out of these groups (in particular, no groups may be formed). One condition needs to be met: sticks in each group need to form a triangle. A triangle can be constructed if sum of any two sticks lengths is greater than the third length.

Your are required to partition the sticks so that the sum of triangle areas from all the groups is maximized.

Input

Very first line of the input contains integer T: number of test cases (1 <= T <= 5).

For each test case, first line contains integer N: number of sticks. (1 <= N <= 15).

Second line contains N space separated integers: the lengths li of the sticks. (1 <= li <= 10^3, 1 <= i <= N). 

Output

For each test case, output the maximal area in a separate line. Round value to exactly 6 decimal places. Always print exactly 6 decimal places.

Example

Input:
3
3
7 8 5
4
7 8 6 3
3
7 2 1

Output:
17.320508
20.333163
0.000000

Added by:praveen123
Date:2013-08-05
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:

hide comments
2019-03-13 06:26:50
dp and use double instead of float
2017-01-12 15:07:39
13
7 2 1 21 22 23 1000 999 888 7 8 6 3
ans is
a=1000b=999c=888 temp=397588
a=23b=22c=21 temp=208.71
a=8b=7c=7 temp=22.9783
397819.553484


Last edit: 2017-01-12 15:08:08
2015-01-31 07:40:14 Siu Ching Pong (Asuka Kenji)
The questions says:

"A triangle can be constructed if sum of any two sticks lengths is greater than the third length."

But it should be:

"A triangle can be constructed from 3 sticks if the sum of the lengths of the shortest two sticks among any 3 sticks is greater than the length of the third."

Otherwise, a triangle could be constructed from "a = 1, b = 2, c = 4" according to the question, since "4 + 2 > 1".


Last edit: 2015-02-03 07:54:15
2014-06-27 08:24:01 tyson
@praveen123 i m not able to figure out why my code gives wrong answer please provide me with a test case
2013-09-22 18:44:04 u torrent
WA :(

Last edit: 2013-09-22 18:47:29
2013-09-03 03:02:36 praveen123
@:D, thank you for updating the problem statement, Now it looks far better than previous one :)
2013-09-02 16:41:03 :D
Description updated.
2013-08-23 22:56:05 utpal kumar jha
same here getting WA again and again and i am pretty sure my logic's correct and answer for the test case given below is matching with the correct answer.. please provide some more test cases

Last edit: 2013-08-24 12:17:24
2013-08-20 14:29:39 [Lakshman]
I am getting 397587.875000
@Miguel Oliveira can you please check I have posted my code in forum.
Thanks.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.