Chop Chop

reborn BUET Inter University Pro...
Limits 1.5s, 256 MB

There is a convex polygon AA% of nn vertices and you want to divide it into two convex polygons PP and QQ such that their areas are equal (half of AA) and the sum of perimeters of PP and QQ is minimum possible.

Input

The first line of the input is an integer TT which denotes the number of test cases.

For each test case, the first line contains an integer nn, denoting the number of vertices in the polygon AA. nn lines follow, ithi^{th} line containing two real numbers (with four digit precision after decimal point) xi, yix_i, ~y_i denoting the co-ordinate of the ithi^{th} vertex of AA in a counter-clockwise manner.

Constraints:

  • 1T1001 \le T \le 100.

  • 3n2×1053 \le n \le 2 \times 10^5.

  • 107xi, yi107-10^7 \le x_i, ~y_i \le 10^7.

  • Sum of nn across all testcases is less than or equal to 2×1052 \times 10^5.

Output

For each test case, output the minimum total sum of perimeters of PP and QQ on a single line.

Your output will be considered correct if the absolute or relative error is less than or equal to 10610^{-6}.

Sample

InputOutput
1
3
0.0000 0.0000
1000.0000 0.0000
500.0000 1.0000
2002.0019989980

Submit

Login to submit.

Statistics

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