Problem: Complex Paper Folding

Dr. G, an authority in paper folding and one of the directors of Intercultural Consortium on Paper Crafts, believes complexity gives figures beauty. As one of his assistants, your job is to find the way to fold a paper to obtain the most complex figure. Dr. G defines the complexity of a figure by the number of vertices. With the same number of vertices, one with longer perimeter is more complex. To simplify the problem, we consider papers with convex polygon in their shapes and folding them only once. Each paper should be folded so that one of its vertices exactly lies on top of another vertex.

Write a program that, for each given convex polygon, outputs the perimeter of the most complex polygon obtained by folding it once.

Figure 1 (left) illustrates the polygon given in the first dataset of Sample Input. This happens to be a rectangle. Folding this rectangle can yield three different polygons illustrated in the Figures 1-a to c by solid lines. For this dataset, you should answer the perimeter of the pentagon shown in Figure 1-a. Though the rectangle in Figure 1-b has longer perimeter, the number of vertices takes priority.

<image> | <image> | <image> | <image>
---|---|---|---
| (a) | (b) | (c)

Figure 1: The case of the first sample input

Figure 2 (left) illustrates the polygon given in the second dataset of Sample Input, which is a triangle. Whichever pair of its vertices are chosen, quadrangles are obtained as shown in Figures 2-a to c. Among these, you should answer the longest perimeter, which is that of the quadrangle shown in Figure 2-a.

<image> | <image> | <image> | <image>
---|---|---|---
| (a) | (b) | (c)

Figure 2: The case of the second sample input

Although we start with a convex polygon, folding it may result a concave polygon. Figure 3 (left) illustrates the polygon given in the third dataset in Sample Input. A concave hexagon shown in Figure 3 (right) can be obtained by folding it, which has the largest number of vertices.

<image> <image>
Figure 3: The case of the third sample input

Figure 4 (left) illustrates the polygon given in the fifth dataset in Sample Input. Although the perimeter of the polygon in Figure 4-b is longer than that of the polygon in Figure 4-a, because the polygon in Figure 4-b is a quadrangle, the answer should be the perimeter of the pentagon in Figure 4-a.

<image> | <image> | <image>
---|---|---
| (a) | (b)

Figure 4: The case of the fifth sample input

Input

The input consists of multiple datasets, each in the following format.

> n
>  x1 y1
>  ...
>  xn yn
>

n is the number of vertices of the given polygon. n is a positive integer satisfying 3 ≤ n ≤ 20. (xi, yi) gives the coordinates of the i-th vertex. xi and yi are integers satisfying 0 ≤ xi, yi < 1000. The vertices (x1, y1), ..., (xn, yn) are given in the counterclockwise order on the xy-plane with y axis oriented upwards. You can assume that all the given polygons are convex.

All the possible polygons obtained by folding the given polygon satisfy the following conditions.

* Distance between any two vertices is greater than or equal to 0.00001.
* For any three consecutive vertices P, Q, and R, the distance between the point Q and the line passing through the points P and R is greater than or equal to 0.00001.



The end of the input is indicated by a line with a zero.

Output

For each dataset, output the perimeter of the most complex polygon obtained through folding the given polygon. The output value should not have an error greater than 0.00001. Any extra characters should not appear in the output.

Sample Input


4
0 0
10 0
10 5
0 5
3
5 0
17 3
7 10
4
0 5
5 0
10 0
7 8
4
0 0
40 0
50 5
0 5
4
0 0
10 0
20 5
10 5
7
4 0
20 0
24 1
22 10
2 10
0 6
0 4
18
728 997
117 996
14 988
1 908
0 428
2 98
6 54
30 28
106 2
746 1
979 17
997 25
998 185
999 573
999 938
995 973
970 993
910 995
6
0 40
0 30
10 0
20 0
40 70
30 70
0


Output for the Sample Input


23.090170
28.528295
23.553450
97.135255
34.270510
57.124116
3327.900180
142.111776






Example

Input

4
0 0
10 0
10 5
0 5
3
5 0
17 3
7 10
4
0 5
5 0
10 0
7 8
4
0 0
40 0
50 5
0 5
4
0 0
10 0
20 5
10 5
7
4 0
20 0
24 1
22 10
2 10
0 6
0 4
18
728 997
117 996
14 988
1 908
0 428
2 98
6 54
30 28
106 2
746 1
979 17
997 25
998 185
999 573
999 938
995 973
970 993
910 995
6
0 40
0 30
10 0
20 0
40 70
30 70
0


Output

23.090170
28.528295
23.553450
97.135255
34.270510
57.124116
3327.900180
142.111776

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;

template<class T> inline void chmax(T &a, const T &b) { if(a < b) a = b; }

typedef double Real;
constexpr Real EPS = 1e-6;
const Real PI = acos((Real)-1);
inline int sign(Real d) { return d > EPS ? 1 : d < -EPS ? -1 : 0; }

struct point {
	Real x, y;
	explicit point():point(0, 0) {}
	explicit point(Real x_, Real y_):x(x_), y(y_) {}
	point operator+(const point &p) const { return point(x + p.x, y + p.y); }
	point operator-(const point &p) const { return point(x - p.x, y - p.y); }
	point operator*(const point &p) const { return point(x * p.x - y * p.y, x * p.y + y * p.x); }
	point operator*(Real s) const { return point(x * s, y * s); }
	point operator/(Real s) const { return point(x / s, y / s); }
	bool operator<(const point &p) const { return sign(x - p.x) == -1 || (sign(x - p.x) == 0 && sign(y - p.y) == -1); }
	bool operator>(const point &p) const { return sign(x - p.x) == 1 || (sign(x - p.x) == 0 && sign(y - p.y) == 1); }
	bool operator==(const point &p) const { return sign(x - p.x) == 0 && sign(y - p.y) == 0; }
	bool operator!=(const point &p) const { return sign(x - p.x) != 0 || sign(y - p.y) != 0; }
};

inline istream &operator>>(istream &is, point &p) {
	return is >> p.x >> p.y;
}

inline ostream &operator<<(ostream &os, const point &p) {
	return os << '(' << p.x << ", " << p.y << ')';
}

struct line : public array<point, 2> {
	line(const point &a, const point &b) { at(0) = a; at(1) = b; }
};

struct segment : public array<point, 2> {
	segment(const point &a, const point &b) { at(0) = a; at(1) = b; }
};

typedef vector<point> polygon;

inline Real angle(const point &p) {
	return atan2(p.y, p.x);
}

inline Real norm(const point &p) {
	return p.x * p.x + p.y * p.y;
}

inline Real abs(const point &p) {
	return sqrt(norm(p));
}

inline Real dot(const point &a, const point &b) {
	return a.x * b.x + a.y * b.y;
}

inline Real cross(const point &a, const point &b) {
	return a.x * b.y - a.y * b.x;
}

enum { CCW = 1, CW = -1, BACK = 2, FRONT = -2, ON = 0};
inline int ccw(const point &a, const point &b, const point &c) {
	const point p = b - a;
	const point q = c - a;
	const int sign_cross = sign(cross(p, q));
	if(sign_cross == 1) return CCW;
	if(sign_cross == -1) return CW;
	if(sign(dot(p, q)) == -1) return BACK;
	if(sign(norm(p) - norm(q)) == -1) return FRONT;
	return ON;
}

inline point project(const line &l, const point &p) {
	const point a = p - l[0];
	const point b = l[1] - l[0];
	return l[0] + b * (dot(a, b) / norm(b));
}

inline point reflect(const line &l, const point &p) {
	const point t = project(l, p);
	return t + (t - p);
}

inline bool intersect(const segment &s, const point &p) {
	return ccw(s[0], s[1], p) == ON;
}

inline bool intersect(const segment &a, const segment &b) {
	return ccw(a[0], a[1], b[0]) * ccw(a[0], a[1], b[1]) <= 0
		&& ccw(b[0], b[1], a[0]) * ccw(b[0], b[1], a[1]) <= 0;
}

inline bool intersect(const line &a, const line &b) {
	return sign(cross(a[1] - a[0], b[1] - b[0])) != 0 // not parallel
		|| sign(cross(a[1] - a[0], b[1] - a[0])) == 0; // same line
}

inline Real dist(const point &a, const point &b) {
	return abs(a - b);
}

inline point crosspoint(const line &a, const line &b) {
	assert(intersect(a, b));
	const Real crs = cross(a[1] - a[0], b[1] - b[0]);
	if(sign(crs) == 0) return a[0]; // same line
	return b[0] + (b[1] - b[0]) * (cross(a[1] - a[0], a[1] - b[0]) / crs);
}

inline point crosspoint(const segment &a, const segment &b) {
	assert(intersect(a, b));
	const Real crs = cross(a[1] - a[0], b[1] - b[0]);
	if(sign(crs) == 0) { // on same line
		if(intersect(a, b[0])) return b[0];
		if(intersect(a, b[1])) return b[1];
		if(intersect(b, a[0])) return a[0];
		return a[1];
	}
	return b[0] + (b[1] - b[0]) * (cross(a[1] - a[0], a[1] - b[0]) / crs);
}

inline Real area(const polygon &P) {
	Real res = 0;
	for(int i = 0; i < P.size(); ++i) {
		res += cross(P[i], P[(i + 1) % P.size()]);
	}
	return res * 0.5;
}

inline line bisector(const point &a, const point &b) {
	return line(point((a.x - a.y + b.x + b.y) * 0.5, (a.y + a.x + b.y - b.x) * 0.5),
				point((a.x + a.y + b.x - b.y) * 0.5, (a.y - a.x + b.y + b.x) * 0.5));
}

inline polygon convex_cut(const polygon &P, const line &l) {
	polygon res;
	for(int i = 0; i < P.size(); ++i) {
		const point &curr = P[i];
		const point &next = P[(i + 1) % P.size()];
		const int curr_ccw = ccw(l[0], l[1], curr);
		const int next_ccw = ccw(l[0], l[1], next);
		if(curr_ccw != -1) res.emplace_back(curr);
		if(curr_ccw * next_ccw < 0) res.emplace_back(crosspoint(l, line(curr, next)));
	}
	return res;
}

inline void merge(vector<segment> &segments) {
	for(int i = 0; i < segments.size(); ) {
		const segment &s1 = segments[i];
		bool ok = true;
		for(int j = i + 1; j < segments.size(); ++j) {
			const segment &s2 = segments[j];

			if(intersect(s1, s2) && sign(cross(s1[0] - s1[1], s2[0] - s2[1])) == 0) {
				const point a = min({s1[0], s1[1], s2[0], s2[1]});
				const point b = max({s1[0], s1[1], s2[0], s2[1]});
				segments.emplace_back(a, b);
				segments.erase(segments.begin() + j);
				segments.erase(segments.begin() + i);
				ok = false;
				break;
			}
		}
		if(ok) ++i;
	}
}

struct edge {
	int to;
	Real theta;
	bool used;
	edge(int to_, Real theta_):to(to_), theta(theta_), used(false) {}
	bool operator<(const edge &e) const { return theta < e.theta; }
};

typedef vector<vector<edge>> graph;
graph arrangement(vector<segment> &segments, vector<point> &points) {
	merge(segments);
	const int n = segments.size();
	points.clear();

	for(int i = 0; i < n; ++i) {
		const segment &s1 = segments[i];
		points.emplace_back(s1[0]);
		points.emplace_back(s1[1]);

		for(int j = i + 1; j < n; ++j) {
			const segment &s2 = segments[j];
			if(intersect(s1, s2)) points.emplace_back(crosspoint(s1, s2));
		}
	}

	sort(begin(points), end(points));
	points.erase(unique(begin(points), end(points)), end(points));

	const int V = points.size();
	graph G(V);
	for(const segment &s : segments) {
		vector<pair<Real, int>> vs;
		for(int i = 0; i < V; ++i) {
			if(intersect(s, points[i])) vs.emplace_back(norm(s[0] - points[i]), i);
		}

		sort(begin(vs), end(vs));
		for(int i = 1; i < vs.size(); ++i) {
			const int v = vs[i].second;
			const int u = vs[i - 1].second;
			G[v].emplace_back(u, angle(points[u] - points[v]));
			G[u].emplace_back(v, angle(points[v] - points[u]));
		}
	}
	for(vector<edge> &edges : G) sort(edges.rbegin(), edges.rend());
	return G;
}

polygon get_outside(graph &G, const vector<point> &points) {
	const int V = G.size();
	for(int i = 0; i < V; ++i) {
		for(int j = 0; j < G[i].size(); ++j) {
			int v = i;
			int e_idx = j;
			polygon P;

			while(true) {
				edge &e = G[v][e_idx];
				if(e.used) break;

				e.used = true;
				P.emplace_back(points[v]);
				for(int k = 0; k < G[e.to].size(); ++k) {
					if(G[e.to][k].to == v) {
						v = e.to;
						e_idx = (k + 1) % G[e.to].size();
						break;
					}
				}
			}

			if(P.size() >= 3 && sign(area(P)) == -1) return P;
		}
	}
	assert(false);
}

polygon reflect(const polygon &P, const line &l) {
	polygon res;
	res.reserve(P.size());
	for(const auto &p : P) {
		res.emplace_back(reflect(l, p));
	}
	return res;
}

int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout.setf(ios::fixed);
	cout.precision(15);

	for(int n; cin >> n && n;) {
		polygon P(n);
		for(auto &e : P) cin >> e;

		pair<int, Real> ans(0, 0.0);
		for(int i = 0; i < n; ++i) {
			for(int j = i + 1; j < n; ++j) {
				const line l = bisector(P[i], P[j]);
				const polygon P1 = convex_cut(P, l);
				const polygon P2 = reflect(convex_cut(P, line(l[1], l[0])), l);

				vector<segment> segments;
				for(int k = 0; k < P1.size(); ++k) {
					segments.emplace_back(P1[k], P1[(k + 1) % P1.size()]);
				}

				for(int k = 0; k < P2.size(); ++k) {
					segments.emplace_back(P2[k], P2[(k + 1) % P2.size()]);
				}

				vector<point> points;
				graph G = arrangement(segments, points);
				const polygon outside = get_outside(G, points);

				int m = outside.size();
				Real len = 0.0;
				for(int k = 0; k < outside.size(); ++k) {
					const point &prev = outside[(k - 1 + outside.size()) % outside.size()];
					const point &curr = outside[k];
					const point &next = outside[(k + 1) % outside.size()];
					len += dist(curr, next);
					if(ccw(prev, curr, next) == FRONT) --m;
				}
				chmax(ans, make_pair(m, len));
			}
		}

		cout << ans.second << endl;
	}

	return EXIT_SUCCESS;
}