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++