Escape from Misty Mountains
Bilbo Baggins, a burglar in the company of 13 dwarves, has unfortunately been separated from the others. While looking for a way out of the tunnels of the Misty Mountains he meets Gollum. But Gollum doesn't want to help Bilbo, he wants to eat him! So they decide to play a game.
Gollum has N wooden sticks in his tunnel, all of different lengths. Bilbo has to choose any 3 sticks at random and has to give them to Gollum. If Gollum is unable to form a triangle Bilbo will win the game and Gollum will show him the way out. Otherwise, Gollum will eat him.
Given the lengths of the N wooden sticks, find the probability that Bilbo wins the game.
The first line of input indicates the number of test cases, t. Each test case will have 2 lines, the first line indicates n, the number of wooden sticks Gollum has, and the next line indicates the n space separated lengths of the sticks.
The Output for each test case is a single decimal value between 0 and 1 indicating the probability that Bilbo wins the game in that instance. The value should be precise upto 4 decimal places.
1 6 7 2 5
8 3 15 4 9 20
1 4 8 6 19 12 10
Length of a stick l must be between 1 and 1,000,000
Note : If the 3 sticks chosen by Bilbo form a degenerate triangle he will not win. A degenerate triangle is one where one side is exactly equal to the sum of the other two sides. For example, sticks of lengths 1,2 and 3 form a degenerate triangle because 1+2=3.
Problem Setter : Neesha Sinha