chakravyuha

The Kauravas challenge the Pandavas to break a circular battle formation known as the Chakravyuha. The Pandavas accept the challenge since they know that the knowledge of how to defeat such a formation is known to Krishna and Arjuna. However, on that day, Krishna and Arjuna are dragged into fighting a war on another front with the Samsaptakas. Since the Pandavas have accepted the challenge already, Abhimanyu decided to attempt the challenge. Abhimanyu used his skills to successfully break into the formation. Abhimanyu fights valiantly single-handedly slaying several warriors who come his way including Duryodhana's son Laxman. Upon witnessing the death of his beloved son, Duryodhana is incensed and orders the entire Kaurava force to attack Abhimanyu. Drona suggests that Abhimanyu could only be killed through illicit means His comments are met with agreement, Salya snaps Abhimanyu's bow while Dushasana and Kripa kill Abhimanyu's horses and charioteers.  Dronacharya,Aswathama and Karna forms a formation to kill Abhimanu. As Abhimanu is a highly skilled warrior this formation will work only if Abhimanu lies within or on the UNIQUE CIRCLE formed by these warriors.
All four individuals, i.e. Dronacharya,Aswathama, Karna and Abhimanyu stands on different position in the formation. 
There may be several ways in which this formation can be made. You may assume that the all Kauravas are indistinguishable, while considering how many ways can everyone be placed. Any one of these ways now, is equiprobable. 
What is the probability that Abhimanyu can be killed by Kauravas in Chakravyuha.

Input
The first line of the input contains an integer T, the number of test cases. The description of T test cases follows. 
The first line of each test case contains a single integer N, the number of positions in chakravyuha formation. 
The next N lines consist of 2 space separated integers each, where the i'th line specifies the X and Y co-ordinates of the i'th position in chakravyuha. 
Output
For each test case, output a single line containing the probability that Abhimanyu is killed in Chakravyuha. 
Your answer should be round up to 6 decimal places. 

Constraints
1 ≤ T ≤ 10
4 ≤ N ≤ 30
-50 ≤ X, Y ≤ 50
All (X,Y) in a test case are unique.

SAMPLE INPUT
2
4
0 0
-2 0
2 0
0 2
5
0 0
-3 0
3 0
0 -3
0 3

SAMPLE OUTPUT
0.250000
0.400000

Explanation

Test 1: 
There are 4 ways Kauravas may be placed. Each one of them has the probability 0.25, of occurring.
•   Let { (-2,0), (0,0), (0,2) } be formation made by kauravas, Abhimanyu is at (2,0). Abhimanyu cannot be killed even though Kauravas formed has a valid and unique circular formation.
•   Let  { (-2,0), (0,0), (2,0) } be formation made by kauravas,  Abhimanyu is at (0,2). Abhimanyu cannot be killed because Kauravas does not have a unique circular formation.
•   Let  { (-2,0), (0,2), (2,0) } be formation made by kauravas, Abhimanyu is at (0,0). Abhimanyu can be killed since he is standing inside Kauravas unique circular formation.
•   Let { (0,0), (0,2), (2,0) } be formation made by kauravas, Abhimanyu is at (-2,0). Abhimanyu cannot be killed even though Kauravas has a valid and unique circular formation.

Test 2: 
There are 10 ways Kauravas may be placed. Each one of them has the probability 0.1, of occurring. For each one of those placements, Abhimanyu may be placed at one of the 2 remaining positions. Thus, with probability 0.05 each, there are 20 total arrangements to consider. Abhimanyu can be killed by Kauravas in 8 of these 20 cases.

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: