Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Sticking Pins

By zobayer · 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


Discussion
Statistics

75% Solution Ratio

KnightMareEarliest, Jul '18

AashiqFastest, 16169.5s

KnightMareLightest, 131 kB

bertho_coderShortest, 1941B

Submit

Login to submit