Complex Paper Folding

Dr. G studies paper folding and measures the beauty of a figure by its complexity. The complexity of a figure is the number of its vertices. Between two figures with the same number of vertices, the one with the longer perimeter is more complex.

Every sheet of paper here is a convex polygon, and it is folded exactly once. The fold has to put one vertex of the paper exactly on top of another vertex. Pick two distinct vertices $A$ and $B$. The crease is the perpendicular bisector of the segment $AB$, and it cuts the paper into two parts. Reflect the part that holds $A$ across the crease and lay it over the other part. The figure after folding is the union of the part that stayed and the reflected part. Folding the $B$ side instead gives the mirror image of that figure, so it has the same number of vertices and the same perimeter.

Write a program that, for each given convex polygon, prints the perimeter of the most complex polygon that one fold can produce.

The first dataset of the example input is a rectangle, drawn on the left of Figure 1. Folding it gives the three polygons drawn with solid lines in Figures 1-a to 1-c. The answer for this dataset is the perimeter of the pentagon in Figure 1-a. The rectangle in Figure 1-b has a longer perimeter, but the number of vertices comes first.

Given polygon	(a)	(b)	(c)

Figure 1: the first dataset of the example input

The second dataset is a triangle, drawn on the left of Figure 2. Whichever pair of vertices you pick, you get a quadrangle, as in Figures 2-a to 2-c. The answer is the longest perimeter among them, which belongs to the quadrangle in Figure 2-a.

Given polygon	(a)	(b)	(c)

Figure 2: the second dataset of the example input

The paper starts convex, but folding it can produce a concave polygon. Figure 3 (left) is the polygon of the third dataset. Folding it can produce the concave hexagon on the right of Figure 3, which has the largest number of vertices.

Given polygon	Folded figure

Figure 3: the third dataset of the example input

Figure 4 (left) is the polygon of the fifth dataset. The polygon in Figure 4-b has a longer perimeter than the one in Figure 4-a, but it is a quadrangle, so the answer is the perimeter of the pentagon in Figure 4-a.

Given polygon	(a)	(b)

Figure 4: the fifth dataset of the example input

The input holds several datasets. Each dataset has the following format.

n
x1 y1
...
xn yn

$n$ is the number of vertices of the given polygon, and it satisfies $3 \le n \le 20$. $(x_i, y_i)$ is the position of the $i$-th vertex. $x_i$ and $y_i$ are integers with $0 \le x_i, y_i < 1000$. The vertices $(x_1, y_1), \dots, (x_n, y_n)$ are listed counterclockwise on the $xy$ plane with the $y$ axis pointing up. Every given polygon is convex.

Every polygon obtainable by folding a given polygon meets these two conditions.

• The distance between any two of its vertices is at least $0.00001$.
• For any three consecutive vertices $P$, $Q$, $R$, the distance between the point $Q$ and the line through $P$ and $R$ is at least $0.00001$.

A line holding a single zero ends the input.

For each dataset, print on one line the perimeter of the most complex polygon obtained by folding the given polygon once. Print exactly six digits after the decimal point, and print nothing else. Every answer in the test data is far enough from a rounding boundary that the sixth digit is unambiguous.