Sticking Pins

zobayer AB Bank IUT 8th ICT Fest...
Limits 1s, 512 MB

You are sticking pins on a 2D board at N given coordinates. However, since you are not very good at sticking pins, once you try to hang the board on the wall, some pins might just fall off. You will be given the probabilities that a pin might fall off from the board. The events that represent the falling of individual pins are mutually independent.

Once the board is on the wall, you want to find the area of the convex hull composed of the pins which are still on the board. Determine the expected value of this area.

Input

First line of input is an integer T (T < 100), number of test cases. For each test cases, you will be given N (3 <= N <= 100), the number of initial points, followed by N triplets of floating point numbers x, y, p which represents the coordinate of the point (x, y) and the probability p that the pin may fall off. Here, -1000.0 <= x, y <= 1000.0 and 0.0 <= p <= 1.0.

Output

For each test case, print a line containing the expected value of the area. Floating point errors smaller than 1e-4 will be allowed by the judge. Please check sample input and output for details.

Sample

InputOutput
3
3
0.00 0.00 0.500
0.00 1.00 0.500
1.00 0.00 0.500
4
0.00 0.00 0.000
1.00 0.00 0.000
0.00 1.00 0.600
1.00 1.00 0.200
5
0.00 0.00 0.000
0.00 1.00 0.500
1.00 2.00 0.800
2.00 1.00 0.500
2.00 0.00 0.000
0.062500
0.600000
1.300000

Submit

Login to submit.

Statistics

100% Solution Ratio
iutictf8.23$moJxCEarliest, Nov '16
Deshi_TouristFastest, 0.0s
iutictf8.23$moJxCLightest, 131 kB
sahedsohelShortest, 1579B
Toph uses cookies. By continuing you agree to our Cookie Policy.