#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<list>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<string>
#define sgn(v) (abs((v))<eps?0:((v)<0?-1:1))
#define sqr(v) ((v)*(v))
#define mb make_pair
#define debug 0
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<int,LL> PIL;
typedef pair<LL,int> PLI;
typedef pair<LL,LL> PLL;
const double eps=1e-8;
const double pi=acos(-1);
const int maxn=101;
struct Point
{
	double x,y;
	Point(){}
	Point(double X,double Y)
	{
		x=X;y=Y;
	}
	bool operator <(const Point &p)const
	{
		if(sgn(x-p.x))return x<p.x;
		else return y<p.y;
	}
	bool operator ==(const Point &p)const
	{
		return sgn(x-p.x)==0&&sgn(y-p.y)==0;
	}
	Point operator -(const Point &p)
	{
		return Point(x-p.x,y-p.y);
	}
	Point operator +(const Point &p)
	{
		return Point(x+p.x,y+p.y);
	}
	double cross(const Point &p)const
	{
		return x*p.y-y*p.x;
	}
	double len()
	{
		return sqrt(sqr(x)+sqr(y));
	}
	void unit()
	{
		double tmp=len();
		x/=tmp;
		y/=tmp;
		x*=0.0001;
		y*=0.0001;
	}
}pt[maxn];
struct Segment
{
	Point st,ed;
};
double cross(const Point &p,const Point &q)
{
	return p.x*q.y-p.y*q.x;
}
double dot(const Point &p,const Point &q)
{
	return p.x*q.x+p.y*q.y;
}
Point Insect(Segment &p,Segment &q)
{
	double u=cross(p.ed-p.st,q.st-p.st),v=cross(p.st-p.ed,q.ed-p.st);
	return Point((q.st.x*v+q.ed.x*u)/(u+v),(q.st.y*v+q.ed.y*u)/(u+v));
}
vector<Point> tp,sp;
int n,cas;
double go[][2]={{19942705,57051994},{-19942705,57051994},{19942705,-57051994},{-19942705,-57051994},{-19942705,27051994},{19942705,27051994},{19942705,-27051994},{-19942705,-27051994}};
int check(Point P,int deb)
{
	int avg=0,con;
	Segment now,tmp;
	Point cp;
	now.st=P;
	if(deb)cout <<P.x<<" "<<P.y<<endl;
	for(int j=0;j<1;++j)
	{
		con=0;
		now.ed.x=P.x+go[j][0];
		now.ed.y=P.y+go[j][1];
		for(int i=0;i<n;++i)
		{
			tmp.st=pt[i];
			tmp.ed=pt[(i+1)%n];
			if(sgn((tmp.ed-tmp.st).cross(now.ed-now.st)))
			{
				cp=Insect(tmp,now);
				if(sgn(dot(tmp.ed-cp,cp-tmp.st))>0&&sgn(dot(now.ed-cp,cp-now.st))>0)
				{
					if(deb)
					cout <<j<<" "<<"cross point:"<<cp.x<<" "<<cp.y<<" when:"<<tmp.st.x<<" "<<tmp.st.y<<" "<<tmp.ed.x<<" "<<tmp.ed.y<<endl;
					++con;
				}
			}
		}
	}
	if(deb)cout <<"avg: "<<avg<<endl;
	return con%2;
}
	
double check(int i,int j)
{
	int oi=i,oj=j;
	Segment now,tmp;
	Point cp;
	tp.clear();
	now.st=pt[i];
	now.ed=pt[j];
	//cout <<"------------Begin--------------"<<endl;cout <<now.st.x<<" "<<now.st.y<<endl;cout <<now.ed.x<<" "<<now.ed.y<<endl;
	for(i=0;i<n;++i)
	{
		tmp.st=pt[i];
		tmp.ed=pt[(i+1)%n];
		//cout <<tmp.st.x<<" "<<tmp.st.y<<endl;cout <<tmp.ed.x<<" "<<tmp.ed.y<<endl;
		//cout <<(tmp.ed-tmp.st).cross(now.ed-now.st)<<endl;
		if(sgn((tmp.ed-tmp.st).cross(now.ed-now.st)))
		{
			cp=Insect(tmp,now);
			//cout <<"HERE"<<" "<<cp.x<<" "<<cp.y<<" "<<dot(tmp.ed-cp,cp-tmp.st)<<endl;
			if(sgn(dot(tmp.ed-cp,cp-tmp.st))>0)
				tp.push_back(cp);
			else if(sgn(dot(tmp.ed-cp,cp-tmp.st))==0)
			{
				if(cp==tmp.st)j=i;
				else j=i+1;
				if(cross(pt[(j-1+n)%n]-now.st,now.ed-now.st)*cross(pt[(j+1)%n]-now.st,now.ed-now.st)<0)
				{

					//if(cas==12&&oi==12&&oj==33)cout <<"cp:"<<cp.x<<" "<<cp.y<<endl;
					tp.push_back(cp);
				}
			}
		}
		else if(sgn((now.st-tmp.st).cross(now.ed-now.st))==0&&sgn((now.st-tmp.ed).cross(now.ed-now.st))==0)
		{
			Point vec=tmp.ed-tmp.st;
			vec.unit();
			if(cross(pt[(i-1+n)%n]-now.st,now.ed-now.st)*cross(pt[(i+2)%n]-now.st,now.ed-now.st)<0)
			{
				//if(cas==12&&oi==0&&oj==61)check(tmp.st-vec,1);
				if(!check(tmp.st-vec,0))
					tp.push_back(tmp.st);
				if(!check(tmp.ed+vec,0))
					tp.push_back(tmp.ed);
			}
		}
	}
	sort(tp.begin(),tp.end());
	if(cas==-1&&oi==0&&oj==61){cout <<"0--tp--0"<<endl;for(i=0;i<tp.size();++i)cout<<tp[i].x<<" "<<tp[i].y<<endl;cout <<"0--end--0"<<endl;}
	int n=tp.size();
	sp.clear();
	for(i=0;i<n;++i)
		if(i==0||(!(tp[i]==tp[i-1])))sp.push_back(tp[i]);
	if(cas==-1&&oi==0&&oj==61){cout <<"0--sp--0"<<endl;for(i=0;i<sp.size();++i)cout<<sp[i].x<<" "<<sp[i].y<<endl;cout <<"0--end--0"<<endl;}
	double ans=0;
	for(i=0;i<sp.size();i+=2)
		ans=max(ans,(sp[i+1]-sp[i]).len());
	return ans;
}
int main()
{
	int i,j;
	cas=0;
	while(scanf("%d",&n)!=EOF)
	{
		if(n==0)break;
		//if(cas==12)cout <<n<<endl;
		double len=0;
		for(i=0;i<n;++i)
		{
			scanf("%lf%lf",&pt[i].x,&pt[i].y);
			//if(cas==12)cout <<pt[i].x<<" "<<pt[i].y<<endl;
		}
		for(i=0;i<n;++i)
			len=max(len,(pt[i]-pt[(i+1)%n]).len());
		for(i=0;i<n;++i)
			for(j=i+1;j<n;++j)
			{
				if(cas==-1)
				{
					if(len<check(i,j))
						cout <<len<<" "<<check(i,j)<<" "<<i<<" "<<j<<" "<<endl
							 <<pt[i].x<<" "<<pt[i].y<<endl
							 <<pt[j].x<<" "<<pt[j].y<<endl
							 <<"----------------------------------------------------"<<endl;
				}
				len=max(len,check(i,j));
			}
		printf("Case %d: %.10f\n",++cas,len);
		//cout <<len*len<<endl;
	}
	return 0;
}
### Prompt

Create a solution in CPP for the following problem:

Mr. KM, the mayor of KM city, decided to build a new elementary school. The site for the school has an awkward polygonal shape, which caused several problems. The most serious problem was that there was not enough space for a short distance racetrack. Your task is to help Mr. KM to calculate the maximum possible length for the racetrack that can be built in the site. The track can be considered as a straight line segment whose width can be ignored. The boundary of the site has a simple polygonal shape without self-intersection, and the track can touch the boundary. Note that the boundary might not be convex.



Input

The input consists of multiple test cases, followed by a line containing "0". Each test case has the following format. The first line contains an integer N (3 \leq N \leq 100). Each of the following N lines contains two integers x_i and y_i (-1,000 \leq x_i, y_i \leq 1,000), which describe the coordinates of a vertex of the polygonal border of the site, in counterclockwise order.

Output

For each test case, print its case number and the maximum possible length of the track in a line. The answer should be given as a floating point number with an absolute error of at most 10^{-6}.

Example

Input

4
0 0
10 0
10 10
0 10
3
0 0
1 0
0 1
0


Output

Case 1: 14.142135624
Case 2: 1.41421356

### Response

```cpp
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<list>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<string>
#define sgn(v) (abs((v))<eps?0:((v)<0?-1:1))
#define sqr(v) ((v)*(v))
#define mb make_pair
#define debug 0
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<int,LL> PIL;
typedef pair<LL,int> PLI;
typedef pair<LL,LL> PLL;
const double eps=1e-8;
const double pi=acos(-1);
const int maxn=101;
struct Point
{
	double x,y;
	Point(){}
	Point(double X,double Y)
	{
		x=X;y=Y;
	}
	bool operator <(const Point &p)const
	{
		if(sgn(x-p.x))return x<p.x;
		else return y<p.y;
	}
	bool operator ==(const Point &p)const
	{
		return sgn(x-p.x)==0&&sgn(y-p.y)==0;
	}
	Point operator -(const Point &p)
	{
		return Point(x-p.x,y-p.y);
	}
	Point operator +(const Point &p)
	{
		return Point(x+p.x,y+p.y);
	}
	double cross(const Point &p)const
	{
		return x*p.y-y*p.x;
	}
	double len()
	{
		return sqrt(sqr(x)+sqr(y));
	}
	void unit()
	{
		double tmp=len();
		x/=tmp;
		y/=tmp;
		x*=0.0001;
		y*=0.0001;
	}
}pt[maxn];
struct Segment
{
	Point st,ed;
};
double cross(const Point &p,const Point &q)
{
	return p.x*q.y-p.y*q.x;
}
double dot(const Point &p,const Point &q)
{
	return p.x*q.x+p.y*q.y;
}
Point Insect(Segment &p,Segment &q)
{
	double u=cross(p.ed-p.st,q.st-p.st),v=cross(p.st-p.ed,q.ed-p.st);
	return Point((q.st.x*v+q.ed.x*u)/(u+v),(q.st.y*v+q.ed.y*u)/(u+v));
}
vector<Point> tp,sp;
int n,cas;
double go[][2]={{19942705,57051994},{-19942705,57051994},{19942705,-57051994},{-19942705,-57051994},{-19942705,27051994},{19942705,27051994},{19942705,-27051994},{-19942705,-27051994}};
int check(Point P,int deb)
{
	int avg=0,con;
	Segment now,tmp;
	Point cp;
	now.st=P;
	if(deb)cout <<P.x<<" "<<P.y<<endl;
	for(int j=0;j<1;++j)
	{
		con=0;
		now.ed.x=P.x+go[j][0];
		now.ed.y=P.y+go[j][1];
		for(int i=0;i<n;++i)
		{
			tmp.st=pt[i];
			tmp.ed=pt[(i+1)%n];
			if(sgn((tmp.ed-tmp.st).cross(now.ed-now.st)))
			{
				cp=Insect(tmp,now);
				if(sgn(dot(tmp.ed-cp,cp-tmp.st))>0&&sgn(dot(now.ed-cp,cp-now.st))>0)
				{
					if(deb)
					cout <<j<<" "<<"cross point:"<<cp.x<<" "<<cp.y<<" when:"<<tmp.st.x<<" "<<tmp.st.y<<" "<<tmp.ed.x<<" "<<tmp.ed.y<<endl;
					++con;
				}
			}
		}
	}
	if(deb)cout <<"avg: "<<avg<<endl;
	return con%2;
}
	
double check(int i,int j)
{
	int oi=i,oj=j;
	Segment now,tmp;
	Point cp;
	tp.clear();
	now.st=pt[i];
	now.ed=pt[j];
	//cout <<"------------Begin--------------"<<endl;cout <<now.st.x<<" "<<now.st.y<<endl;cout <<now.ed.x<<" "<<now.ed.y<<endl;
	for(i=0;i<n;++i)
	{
		tmp.st=pt[i];
		tmp.ed=pt[(i+1)%n];
		//cout <<tmp.st.x<<" "<<tmp.st.y<<endl;cout <<tmp.ed.x<<" "<<tmp.ed.y<<endl;
		//cout <<(tmp.ed-tmp.st).cross(now.ed-now.st)<<endl;
		if(sgn((tmp.ed-tmp.st).cross(now.ed-now.st)))
		{
			cp=Insect(tmp,now);
			//cout <<"HERE"<<" "<<cp.x<<" "<<cp.y<<" "<<dot(tmp.ed-cp,cp-tmp.st)<<endl;
			if(sgn(dot(tmp.ed-cp,cp-tmp.st))>0)
				tp.push_back(cp);
			else if(sgn(dot(tmp.ed-cp,cp-tmp.st))==0)
			{
				if(cp==tmp.st)j=i;
				else j=i+1;
				if(cross(pt[(j-1+n)%n]-now.st,now.ed-now.st)*cross(pt[(j+1)%n]-now.st,now.ed-now.st)<0)
				{

					//if(cas==12&&oi==12&&oj==33)cout <<"cp:"<<cp.x<<" "<<cp.y<<endl;
					tp.push_back(cp);
				}
			}
		}
		else if(sgn((now.st-tmp.st).cross(now.ed-now.st))==0&&sgn((now.st-tmp.ed).cross(now.ed-now.st))==0)
		{
			Point vec=tmp.ed-tmp.st;
			vec.unit();
			if(cross(pt[(i-1+n)%n]-now.st,now.ed-now.st)*cross(pt[(i+2)%n]-now.st,now.ed-now.st)<0)
			{
				//if(cas==12&&oi==0&&oj==61)check(tmp.st-vec,1);
				if(!check(tmp.st-vec,0))
					tp.push_back(tmp.st);
				if(!check(tmp.ed+vec,0))
					tp.push_back(tmp.ed);
			}
		}
	}
	sort(tp.begin(),tp.end());
	if(cas==-1&&oi==0&&oj==61){cout <<"0--tp--0"<<endl;for(i=0;i<tp.size();++i)cout<<tp[i].x<<" "<<tp[i].y<<endl;cout <<"0--end--0"<<endl;}
	int n=tp.size();
	sp.clear();
	for(i=0;i<n;++i)
		if(i==0||(!(tp[i]==tp[i-1])))sp.push_back(tp[i]);
	if(cas==-1&&oi==0&&oj==61){cout <<"0--sp--0"<<endl;for(i=0;i<sp.size();++i)cout<<sp[i].x<<" "<<sp[i].y<<endl;cout <<"0--end--0"<<endl;}
	double ans=0;
	for(i=0;i<sp.size();i+=2)
		ans=max(ans,(sp[i+1]-sp[i]).len());
	return ans;
}
int main()
{
	int i,j;
	cas=0;
	while(scanf("%d",&n)!=EOF)
	{
		if(n==0)break;
		//if(cas==12)cout <<n<<endl;
		double len=0;
		for(i=0;i<n;++i)
		{
			scanf("%lf%lf",&pt[i].x,&pt[i].y);
			//if(cas==12)cout <<pt[i].x<<" "<<pt[i].y<<endl;
		}
		for(i=0;i<n;++i)
			len=max(len,(pt[i]-pt[(i+1)%n]).len());
		for(i=0;i<n;++i)
			for(j=i+1;j<n;++j)
			{
				if(cas==-1)
				{
					if(len<check(i,j))
						cout <<len<<" "<<check(i,j)<<" "<<i<<" "<<j<<" "<<endl
							 <<pt[i].x<<" "<<pt[i].y<<endl
							 <<pt[j].x<<" "<<pt[j].y<<endl
							 <<"----------------------------------------------------"<<endl;
				}
				len=max(len,check(i,j));
			}
		printf("Case %d: %.10f\n",++cas,len);
		//cout <<len*len<<endl;
	}
	return 0;
}
```