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:

unit=0.07cm

(40,60) linestyle=solid linewidth=2pt linecolor=black

(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)

linewidth=1pt linecolor=blue

(00,00)(40,20) (00,00)(30,20) (10,30)(30,20) (10,30)(25,35) (10,30)(40,60) (40,60) linestyle=solid linewidth=2pt linecolor=black

(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)

linewidth=1pt linecolor=blue

(00,00)(40,20) (00,00)(30,20) (10,30)(30,20) (10,30)(25,35) (00,40)(25,35) (40,60) linestyle=solid linewidth=2pt linecolor=black

(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)

linewidth=1pt linecolor=blue

(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 ≤ n ≤ 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++