Shelly's Adventure

Tash52 Intra AUST Programming Co...
Limits 1s, 512 MB

Shelly and her friends have set out on an adventure and have come across an island. The island has a large area. Too large for them to explore together in a single day. The island can be thought of as an 2D space. So they decided to explore individually. But after a few steps they noticed that they cannot remember the area they explored and are exploring the same area multiple times. They thought of a plan to put sticks on the ground in some of their explored places. So if someone comes across a stick placed by them, they know that this area has been explored. Shelly and each of her friends are exploring individually and marking the area that they have explored. The total area explored is the smallest convex polygon that contains all the marking made by them. At the end of the day they meet up to and take a break. Now they want to know the area of the island they explored that day based on their stick marking and wants your help.

Input

The first line of the input will contain an integer T, the number of test cases.

Each test case will consist of a line containing a single integer N, followed by N more lines. Here N is the total number of people including Shelly and her friends. Each of the N lines will contain an integer K, followed by K pair of integers. So the ithi^{th} line contains the number of points K the ithi^{th} person marked and also the location of all the K points (For example KK X1X_{1} Y1Y_{1} X2X_{2} Y2 Y_{2}XKX_{K} YKY_{K}).

1<=T<=201<=T <=20

1<=N<=1001<=N<=100

sum of all K in a single test case <=105<= 10^{5}

1<=Xi,Yi<=1061 <= X_{i}, Y_{i} <= 10^{6}

Output

For each test, output a single line containing the area of the island explored.

The answer will be considered correct if the absolute or relative error doesn't exceed 10610^{-6}.
If the judges answer is P and contestant’s answer is Q then abs(PQ)<=106abs( P-Q ) <= 10^{-6} should hold.

Samples

InputOutput
2
2
3 4 5 6 7 1 10
6 1 2 4 8 1 12 4 3 3 8 7 12
1
7 5 12 1 2 3 5 4 8 3 9 4 2 6 1
45.000000000
31.000000000
InputOutput
1
1
4 0 0 0 6 6 0 6 6
36

Submit

Login to submit.

Statistics

0% Solution Ratio
Toph uses cookies. By continuing you agree to our Cookie Policy.