Cheapest triangulation P65751

Statement

Given a simple polygon with $n$ vertices, there is always at least one way to decompose it in triangles by adding $n - 3$ diagonals. For instance, these are three of the many triangulations of the same polygon:

(40,60)

(00,00)(20,00) (20,00)(40,20) (40,20)(30,20) (30,20)(25,35) (25,35)(40,60) (40,60)(00,40) (00,40)(10,30) (10,30)(00,00)

(00,00)(40,20) (00,00)(30,20) (10,30)(30,20) (10,30)(25,35) (10,30)(40,60)

(40,60)

(00,00)(20,00) (20,00)(40,20) (40,20)(30,20) (30,20)(25,35) (25,35)(40,60) (40,60)(00,40) (00,40)(10,30) (10,30)(00,00)

(00,00)(40,20) (00,00)(30,20) (10,30)(30,20) (10,30)(25,35) (00,40)(25,35)

(40,60)

(00,00)(20,00) (20,00)(40,20) (40,20)(30,20) (30,20)(25,35) (25,35)(40,60) (40,60)(00,40) (00,40)(10,30) (10,30)(00,00)

(20,00)(30,20) (20,00)(25,35) (20,00)(10,30) (10,30)(25,35) (10,30)(40,60)

Define the cost of a triangulation as the sum of the lengths of the diagonals that have been added. Given a convex polygon, what is the cost of its cheapest triangulation?

Input

Input consists of several cases. Every case begins with $n$ . Follow $n$ pairs of real numbers $x$ $y$ giving the coordinates of the points of the polygon, either in clockwise or in anticlockwise order. Assume $3 \le n \le 100$ .

Output

For every given polygon, print the cost of its cheapest triangulation with four digits after the decimal point. The input cases have no precision issues.

Public test cases

Input

3   0 0  0 1  1 0
4   0 0  2 0  2 2  0 1
5   -1.2 3  0 4  1 2.7  1 -1  0 -0.5

Output

0.0000
2.2361
5.5730

Information

Author: Salvador Roura
Language: English
Official solutions: C++
User solutions: C++