JustiN diary

[URI Online Judge] – 1717 – Cut

Link: https://www.urionlinejudge.com.br/judge/en/problems/view/1717

Every convex polygon, with 2N vertices, can be decomposed into N − 1 quadrilaterals, by making N − 2 straight line cuts between certain pairs of vertices. The figure below shows three different decompositions of the same polygon with N = 5. The weight of the decomposition is the sum of the lengths of its N −2 cuts. Your program should compute the weight of a minimum weight decomposition!


The input contains several test cases. The first line of a test case contains one integer N (2 ≤ N ≤ 100). The following 2N lines contain, each one, two real numbers X and Y (0 ≤ X, Y ≤ 10000), with precision of 4 decimal digits: the coordinates of the 2N points, in counterclockwise order, of the convex polygon.


    For each test case in the input your program must output one line containing a real number, with 4 decimal digits precision. The number should be the weight of a minimum weight decomposition of the given polygon.

Sample Input Sample Output

5715.7584 3278.6962

3870.5535 4086.7950

3823.2140 4080.7543

3574.4323 170.2905

4521.4796 144.9156

4984.6486 306.2896

5063.1061 347.1661

6099.9959 2095.9358