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>
#define f first
#define s second
#define mp make_pair
#define pi M_PI
#define inf 1<<30
#define eps (1e-6)
#define equals(a,b) (fabs((a)-(b))<eps)
using namespace std;

class Point{
public:
  double x,y;
  Point(double x=0,double y=0):x(x),y(y){}

  Point operator+(Point p){ return Point(x+p.x,y+p.y);}
  Point operator-(Point p){ return Point(x-p.x,y-p.y);}
  Point operator*(double k){ return Point(x*k,y*k);}
  Point operator/(double k){ return Point(x/k,y/k);}
  bool operator<(Point p)const{ return (x!=p.x ? x<p.x : y<p.y);}
  bool operator==(Point p)const{ return fabs(x-p.x)<eps && fabs(y-p.y)<eps;}

  double abs(){ return sqrt(norm());}
  double norm(){ return (x*x+y*y);}
};
typedef Point Vector;
typedef vector<Point> Polygon;

class Segment{
public:
  Point p1,p2;
  Segment(Point p1=Point(),Point p2=Point()):p1(p1),p2(p2){}
};
typedef Segment Line;

double norm(Vector a){ return (a.x*a.x+a.y*a.y);}
double abs(Vector a){ return sqrt(norm(a));}
double dot(Vector a,Vector b){ return (a.x*b.x+a.y*b.y);}
double cross(Vector a,Vector b){ return (a.x*b.y-a.y*b.x);}
double arg(Vector p){ return atan2(p.y,p.x);}

Point project(Segment s,Point p){
  Vector base=(s.p2-s.p1);
  double r=(dot(p-s.p1,base)/base.norm());
  return (s.p1+base*r);
}

Point reflect(Segment s,Point p){
  return p+(project(s,p)-p)*2;
}

bool isParallel(Vector a,Vector b){
  return equals(cross(a,b),0.0);
}

int ccw(Point p0,Point p1,Point p2){
  Vector a=p1-p0;
  Vector b=p2-p0;
  if(cross(a,b)>eps)return 1;
  if(cross(a,b)<-eps)return -1;
  if(dot(a,b)<-eps)return 2;
  if(a.norm()<b.norm())return -2;
  return 0;
}

bool intersect(Point p1,Point p2,Point p3,Point p4){
  return (ccw(p1,p2,p3)*ccw(p1,p2,p4)<=0 &&
          ccw(p3,p4,p1)*ccw(p3,p4,p2)<=0);
}

bool intersect(Segment s1,Segment s2){
  return intersect(s1.p1,s1.p2,s2.p1,s2.p2);
}

Point getCrossPointSS(Segment s1,Segment s2){
  Vector base=s2.p2-s2.p1;
  double d1=abs(cross(base,s1.p1-s2.p1));
  double d2=abs(cross(base,s1.p2-s2.p1));
  double t=d1/(d1+d2);
  return (s1.p1+(s1.p2-s1.p1)*t);
}

Point getCrossPointLL(Line a,Line b){
  double A=cross(a.p2-a.p1,b.p2-b.p1);
  double B=cross(a.p2-a.p1,a.p2-b.p1);
  if(abs(A)<eps || abs(B)<eps)return b.p1;
  return b.p1+(b.p2-b.p1)*(B/A);
}

Line getPerpendicularBisector(Segment s){
  Point m=s.p1+(s.p2-s.p1)/2.0;
  Vector v1=s.p1-m,v2=s.p2-m;
  swap(v1.x,v1.y);
  v1.x=-v1.x;
  swap(v2.x,v2.y);
  v2.x=-v2.x;
  return Line(m+v1,m+v2);
}

int contains(Polygon g,Point p){
  int n=g.size();
  bool x=false;
  for(int i=0;i<n;i++){
    Vector a=g[i]-p,b=g[(i+1)%n]-p;
    if(abs(cross(a,b))<eps && dot(a,b)<eps)return 1;
    if(a.y>b.y)swap(a,b);
    if(a.y<eps && eps<b.y && cross(a,b)>eps)x=!x;
  }
  if(x)return 2;
  return 0;
}

Polygon convex_cut(Polygon p,Line l){
  Polygon ans;
  for(int i=0;i<p.size();i++){
    Point A=p[i],B=p[(i+1)%p.size()];
    if(ccw(l.p1,l.p2,A)!=-1)ans.push_back(A);
    if(ccw(l.p1,l.p2,A)*ccw(l.p1,l.p2,B)<0)
      ans.push_back(getCrossPointLL(l,Segment(A,B)));
  }
  return ans;
}

double getCircumference(Polygon p){
  double res=0;
  int n=p.size();
  for(int i=0;i<n;i++)res+=abs(p[i]-p[(i+1)%n]);
  return res;
}

typedef pair<int,double> pid;

vector<Point> unique(vector<Point> vp){
  sort(vp.begin(),vp.end());
  vector<Point> res;
  res.push_back(vp[0]);
  for(int i=1;i<vp.size();i++){
    if(!(vp[i]==res.back()))res.push_back(vp[i]);
  }
  return res;
}

Polygon erase(Polygon vp){
  Polygon res;
  int n=vp.size();
  for(int i=0;i<n;i++){
    Point p0=vp[i],p1=vp[(i+1)%n],p2=vp[(i+2)%n];
    if(ccw(p0,p2,p1)!=0)res.push_back(p1);
  }
  return res;
}

Polygon getReflectPolygon(Polygon p,Line L){
  Polygon res;
  for(int i=0;i<p.size();i++)res.push_back(reflect(L,p[i]));
  reverse(res.begin(),res.end());
  return res;
}

Polygon PolygonFolding(Polygon p,Line L){
  Polygon p1=convex_cut(p,L),p2=convex_cut(p,Line(L.p2,L.p1));
  p2=getReflectPolygon(p2,L);
  Polygon res,sets;
  for(int i=0;i<p1.size();i++){
    Segment s1(p1[i],p1[(i+1)%p1.size()]);
    for(int j=0;j<p2.size();j++){
      Segment s2(p2[j],p2[(j+1)%p2.size()]);
      if(isParallel(s1.p1-s1.p2,s2.p1-s2.p2))continue;
      if(intersect(s1,s2)){
	Point p=getCrossPointSS(s1,s2);
	if(s1.p1==p || s1.p2==p || s2.p1==p || s2.p2==p)continue;
	sets.push_back(p);
      }
    }
  }
  for(int i=0;i<p1.size();i++){
    int c=ccw(L.p1,L.p2,p1[i]);
    if(c==0 || c==-2 || c==2){
      res.push_back(p1[i]);
    }
  }
  Point tmp=res[0]+(res[1]-res[0])/2.0;
  res.clear();
  for(int i=0;i<p1.size();i++)sets.push_back(p1[i]);
  for(int i=0;i<p2.size();i++)sets.push_back(p2[i]);
  sets=unique(sets);
  vector<pair<double,Point> > vp;
  for(int i=0;i<sets.size();i++){
    double targ=arg(sets[i]-tmp);
    if(targ<0)targ+=2*pi;
    vp.push_back(mp(targ,sets[i]));
  }
  sort(vp.begin(),vp.end());
  for(int i=0;i<vp.size();i++){
    if(contains(p1,vp[i].s)!=2 && contains(p2,vp[i].s)!=2)res.push_back(vp[i].s);
  }
  res=erase(res);
  return res;
}

bool comp(pid a,pid b){
  if(a.f!=b.f)return a.f<b.f;
  return (a.s-b.s)<eps;
}

int main()
{
  int n,x,y;

  while(1){
    cin>>n;
    if(n==0)break;
    Polygon p;
    for(int i=0;i<n;i++){
      cin>>x>>y;
      p.push_back(Point(x,y));
    }
    pid ans(-1,-1);
    for(int i=0;i<n;i++){
      for(int j=i+1;j<n;j++){
	Line L=getPerpendicularBisector(Segment(p[i],p[j]));
        Polygon tmp=PolygonFolding(p,L);
	pid pii=mp(tmp.size(),getCircumference(tmp));
	if(comp(ans,pii))ans=pii;
      }
    }
    printf("%.10f\n",ans.s);
  }
  return 0;
}