For each movement, a cost is associated, namely the area of the triangle. So, the optimization problem can be restated as the problem of finding a closed path with the minimum sum of the costs in the matrix grid, where each horizontal line on the grid is crossed exactly once by the path, and where each vertical line on the grid is crossed exactly once by the path, as in the figure to the right. The input starts with a single number on a line, N , which stands for the number of test cases. Following this line are the N test cases. The z -coordinates for the vertices in the first polygon is zero.
All coordinates are real numbers.
First are the coordinates for the first polygon, followed by the coordinates for the second polygon. Output For each test case, output the minimum area of the surface connecting the both polygons, using five decimal digits. However, trailing zeros may be omitted. The output is a real number.