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