Spring has finally arrived! (Can't you feel it?!) And this means that it is time for spring cleaning. And spring cleaning means that it is time to clean up our mesh triangulations!
A common task in graphics is mesh triangulation; that is, to “break apart” polygons into sets of triangles. That is because graphics hardware is made to render triangles quickly, but not polygons. But not all triangulations are created equal. For good mesh, we often want to find a best triangulation, one that minimizes a cost.
A triangulation of a convex polygon is made by adding diagonals between non-adjacent vertices — the corners of the polygon — such that the diagonals do not intersect, repeating until the polygon has been divided entirely into triangles.
One measure of cost of a triangluation — call this the perimeter cost — is to sum the lengths of the perimeters of the triangles in the triangluation. The perimeter of a triangle is, of course, the sum of (the lengths) of its three sides. (Note that this is equivalent to the sum of the sides of the polygon, plus twice the sum of the diagonals that you added to get the triangulation, since each diagonal is shared by two triangles.)
Consider the pentagon in the picture. The triangulation on the left has a cost of 8 + 2√2 + 2√5; so, approximately 15.301. The one on the right has a cost of 4 + 2√2 + 4√5; so, approximately 15.773.
The input will consist of a sequence of test cases. The input for each test case starts with a single integer, V, on a line that specifies the number of vertices of the triangle. Following are V lines of two integers each that specify the x,y coordinates of the vertices of the polygon.
The order in which the vertices are given is guaranteed to be a circumoral walk of the polygon. The number of vertices of each test-case polygon will be between 3 and 25, inclusive; 3 ≤ V ≤ 25. Each x & y coordinate of each vertex is between 0 and 1000, inclusive.
The input ends with a line with a single integer 0.
5 0 0 1 0 2 1 1 2 0 2 0
(This is the pentagon from the example above.)
For each test case, output a single line with the cost of the best triangulation by perimeter cost for the polygon. Round this to three digits to the right of the decimal point (and always print the three digits to the right). You are guaranteed no overflows or underflows using the equivalent of double in C++.
15.301