Cheapest triangulation P65751


Statement
 

pdf   zip

thehtml

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