Minimax Triangulation

Time limit1sMemory limit128 MB

Summary

Find the triangulation of a simple polygon minimizing the largest triangle's area, and report that area.

Level: Medium7 of 10
Topics: Dynamic programming, Geometry, Divide and conquer
Solved: No attempts yet

Problem

Triangulating surfaces is useful in the Finite Element Method of solid mechanics: to estimate the stress and strain on a complex object, the object is partitioned into many small, simple pieces that are treated as incompressible. A flat surface is conveniently approximated by a simple polygon — a closed, piecewise-linear curve on $m$ distinct vertices that does not intersect itself.

A chord is a line segment joining two non-adjacent vertices of the polygon that lies entirely inside the polygon; in particular, the only points of a chord that touch the boundary are its two endpoints. A triangulation of the polygon is a choice of $m - 3$ chords that divides the polygon into triangles: no two chosen chords cross except at endpoints, and every remaining (unchosen) chord crosses at least one chosen chord.

Finding some triangulation is easy. The interesting question is finding the best one under a given measure. Here the measure is the area of the largest triangle: among all triangulations, find one whose largest triangle is as small as possible, and report that triangle's area.

Figure 1: Five of the nine possible triangulations of the example polygon. The leftmost one has the smallest largest triangle.

Input

The first line contains a single positive integer $n$ , the number of test scenarios.

Each scenario begins with a line containing one integer $m$ with $2 < m < 50$ , the number of vertices of the simple polygon. Each of the next $m$ lines contains two integers $x$ and $y$ ( $0 \le x \le 10000$ , $0 \le y \le 10000$ ) giving one vertex. The vertices are listed in the order they appear along the boundary, either clockwise or counter-clockwise, starting from an arbitrary vertex.

Output

For each scenario, output a single line with the area of the largest triangle in the triangulation that has the smallest largest triangle. Print the area with exactly one digit after the decimal point.

Because every vertex has integer coordinates, every triangle area is a multiple of $0.5$ , so the answer is always exact (for example, 9.0 or 0.5).

Examples5

Example 1
Input
```
1
6
7 0
6 2
9 5
3 5
0 3
1 1
```
Expected output
```
9.0
```
Example 2
Input
```
1
3
0 0
4 0
0 3
```
Expected output
```
6.0
```
Example 3
Input
```
1
4
0 0
1 0
1 1
0 1
```
Expected output
```
0.5
```
Example 4
Input
```
1
4
0 0
4 0
5 3
1 4
```
Expected output
```
8.0
```
Example 5
Input
```
1
6
0 0
4 0
4 2
2 2
2 4
0 4
```
Expected output
```
4.0
```