#include<bits/stdc++.h>
 
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define EPS (1e-8)
#define COUNTER_CLOCKWISE 1
#define CLOCKWISE -1 
#define ONLINE_BACK 2
#define ONLINE_FRONT -2
#define ON_SEGMENT 0
#define equals(a,b) (fabs((a)-(b)) < EPS)
 
using namespace std;
 
const int IINF = INT_MAX;
 
// template - begin
 
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 a){return Point(a*x,a*y);}
  Point operator / (double a){return Point(x/a,y/a);}
  Point operator * (Point a){ return Point(x * a.x - y * a.y, x * a.y + y * a.x); }
 
  bool operator < (const Point& p) const{ return !equals(x,p.x)?x<p.x:y<p.y; }
  bool operator == (const Point& p)const{ return fabs(x-p.x) < EPS && fabs(y-p.y) < EPS; }
 
};
 
struct Segment{
  Point p1,p2;
  Segment(Point p1 = Point(),Point p2 = Point()):p1(p1),p2(p2){}
  bool operator == (const Segment& p)const { return ( ( p.p1 == p1 && p.p2 == p2 ) || ( p.p1 == p2 && p.p2 == p1 ) ); }
};
 
typedef Point Vector;
typedef Segment Line;
typedef vector<Point> Polygon;
 
ostream& operator << (ostream& os,const Point& a){ os << "(" << a.x << "," << a.y << ")"; }
 
ostream& operator << (ostream& os,const Segment& a){ os << "( " << a.p1 << " , " << a.p2 << " )"; }
 
double dot(Point a,Point b){ return a.x*b.x + a.y*b.y; }
 
double cross(Point a,Point b){ return a.x*b.y - a.y*b.x; }
 
double norm(Point a){ return a.x*a.x+a.y*a.y; }
 
double abs(Point a){ return sqrt(norm(a)); }
 
//rad は角度をラジアンで持たせること
Point rotate(Point a,double rad){ return Point(cos(rad)*a.x - sin(rad)*a.y,sin(rad)*a.x + cos(rad)*a.y); }
 
// 度をラジアンに変換
double toRad(double agl){ return agl*M_PI/180.0; }
 
// a => prev, b => cur, c=> next
// prev から cur へ行って next へ行く際の角度を求める
double getArg(Point a,Point b,Point c){
  double arg1 = atan2(b.y-a.y,b.x-a.x);
  double arg2 = atan2(c.y-b.y,c.x-b.x);
  double arg = fabs( arg1 - arg2 );
  while( arg > M_PI ) arg -= 2.0 * M_PI;
  return fabs(arg);
}
 
// template - end
 
// ccw - begin
 
int ccw(Point p0,Point p1,Point p2){
  Point a = p1-p0;
  Point b = p2-p0;
  if(cross(a,b) > EPS)return COUNTER_CLOCKWISE;
  if(cross(a,b) < -EPS)return CLOCKWISE;
  if(dot(a,b) < -EPS)return ONLINE_BACK;
  if(norm(a) < norm(b))return ONLINE_FRONT;
  return ON_SEGMENT;
}
 
// ccw - end
 
// intersect - begin
 
bool intersectLL(Line l, Line m) {
  return abs(cross(l.p2-l.p1, m.p2-m.p1)) > EPS || // non-parallel
         abs(cross(l.p2-l.p1, m.p1-l.p1)) < EPS;   // same line
}
bool intersectLS(Line l, Line s) {
  return cross(l.p2-l.p1, s.p1-l.p1)*       // s[0] is left of l
         cross(l.p2-l.p1, s.p2-l.p1) < EPS; // s[1] is right of l
}
bool intersectLP(Line l,Point p) {
  return abs(cross(l.p2-p, l.p1-p)) < EPS;
}
bool intersectSS(Line s, Line t) {
  return ccw(s.p1,s.p2,t.p1)*ccw(s.p1,s.p2,t.p2) <= 0 &&
         ccw(t.p1,t.p2,s.p1)*ccw(t.p1,t.p2,s.p2) <= 0;
}
bool intersectSP(Line s, Point p) {
  return abs(s.p1-p)+abs(s.p2-p)-abs(s.p2-s.p1) < EPS; // triangle inequality
}
 
Point projection(Line l,Point p) {
  double t = dot(p-l.p1, l.p1-l.p2) / norm(l.p1-l.p2);
  return l.p1 + (l.p1-l.p2)*t;
}
Point reflection(Line l,Point p) {
  return p + (projection(l, p) - p) * 2;
}
double distanceLP(Line l, Point p) {
  return abs(p - projection(l, p));
}
double distanceLL(Line l, Line m) {
  return intersectLL(l, m) ? 0 : distanceLP(l, m.p1);
}
 
double distanceLS(Line l, Line s) {
  if (intersectLS(l, s)) return 0;
  return min(distanceLP(l, s.p1), distanceLP(l, s.p2));
}
double distanceSP(Line s, Point p) {
  Point r = projection(s, p);
  if (intersectSP(s, r)) return abs(r - p);
  return min(abs(s.p1 - p), abs(s.p2 - p));
}
 
double distanceSS(Line s, Line t) {
  if (intersectSS(s, t)) return 0;
  return min(min(distanceSP(s, t.p1), distanceSP(s, t.p2)),
             min(distanceSP(t, s.p1), distanceSP(t, s.p2)));
}
 
Point crosspoint(Line l,Line m){
  double A = cross(l.p2-l.p1,m.p2-m.p1);
  double B = cross(l.p2-l.p1,l.p2-m.p1);
  if(abs(A) < EPS && abs(B) < EPS){
    vector<Point> vec;
    vec.push_back(l.p1),vec.push_back(l.p2),vec.push_back(m.p1),vec.push_back(m.p2);
    sort(vec.begin(),vec.end());
    assert(vec[1] == vec[2]);
    return vec[1];
    //return m.p1;
  }
  if(abs(A) < EPS)assert(false);
  return m.p1 + (m.p2-m.p1)*(B/A);
}
 
 
// intersect - end
 

// onSegment - being
 
//cross product of pq and pr

double cross3p(Point p,Point q,Point r) { return (r.x-q.x) * (p.y -q.y) - (r.y - q.y) * (p.x - q.x); }
   
//returns true if point r is on the same line as the line pq
bool collinear(Point p,Point q,Point r){ return fabs(cross3p(p,q,r)) < EPS; }
   
//returns true if point t is on the left side of line pq
bool ccwtest(Point p,Point q,Point r){ return cross3p(p,q,r) > 0; }
  
bool onSegment(Point p,Point q,Point r){
  return collinear(p,q,r) && equals(sqrt(pow(p.x-r.x,2)+pow(p.y-r.y,2)) + sqrt(pow(r.x-q.x,2) + pow(r.y-q.y,2) ),sqrt(pow(p.x-q.x,2)+pow(p.y-q.y,2)) ) ;
}

double angle(Point a,Point b,Point c){
  double ux = b.x - a.x, uy = b.y - a.y;
  double vx = c.x - a.x, vy = c.y - a.y;
  return acos((ux*vx + uy*vy)/sqrt((ux*ux + uy*uy) * (vx*vx + vy*vy)));
}  
   
//多角形poly内（線分上も含む）に点pが存在するかどうは判定する  
bool inPolygon(Polygon poly,Point p){
  if((int)poly.size() == 0)return false;

  rep(i,poly.size())
    if(onSegment(poly[i],poly[(i+1)%poly.size()],p))return true;

  double sum = 0;
  for(int i=0; i < (int)poly.size() ;i++){
    if( equals(cross(poly[i]-p,poly[(i+1)%poly.size()]-p),0.0) ) continue; // ３点が平行だとangleがnanを返しsumがnanになり死ぬ
      if( cross3p(p,poly[i],poly[(i+1)%poly.size()]) < 0)
        sum -= angle(p,poly[i],poly[(i+1)%poly.size()]);
      else
        sum += angle(p,poly[i],poly[(i+1)%poly.size()]);
    }
  return (fabs(sum - 2*M_PI) < EPS || fabs(sum + 2*M_PI) < EPS);
}  
 
 
// onSegment - end
 
bool inPolygon(const Polygon &poly,Segment seg){
  vector<Point> vp;
  vp.push_back(seg.p1);
  vp.push_back(seg.p2);
  rep(i,(int)poly.size()) {
    Segment edge = Segment(poly[i],poly[(i+1)%(int)poly.size()]);
    if( equals(cross(seg.p1-edge.p1,seg.p2-edge.p2),0.0) ) {
      if( onSegment(seg.p1,seg.p2,edge.p1) ) vp.push_back(edge.p1);
      if( onSegment(seg.p1,seg.p2,edge.p2) ) vp.push_back(edge.p2);
    } else {
      if( intersectSS(seg,edge) ) vp.push_back(crosspoint(seg,edge));
    }
  }
  sort(vp.begin(),vp.end());
  vp.erase(unique(vp.begin(),vp.end()),vp.end());
  rep(i,(int)vp.size()-1) {
    Point middle_point = ( vp[i] + vp[i+1] ) / 2.0;
    if( !inPolygon(poly,middle_point) ) return false;
  }
  return true;  
}
 
 
const int MAX_N = 110;
int N;
Point ps[MAX_N];
 
bool LTE(double a,double b) { return equals(a,b) || a < b ; } 
 
void compute(){
 
  vector<Point> poly;
  rep(i,N) poly.push_back(ps[i]);
  vector<Segment> segs;
  rep(i,N) segs.push_back(Segment(ps[i],ps[(i+1)%N]));
 
  double ans = 0;
  rep(i,N) REP(j,i+1,N) {

    Line line = Line(ps[i],ps[j]);

    vector<Point> cand;
    cand.push_back(line.p1);
    cand.push_back(line.p2);
    rep(k,N) {
      Segment seg = Segment(ps[k],ps[(k+1)%N]);
      if( !( line == seg ) && intersectLS(line,seg) && !equals(cross(line.p1-line.p2,seg.p1-seg.p2),0.0) ) cand.push_back(crosspoint(line,seg));
    }
    sort(cand.begin(),cand.end());
    cand.erase(unique(cand.begin(),cand.end()),cand.end());

    line.p1 = ps[i], line.p2 = ps[j];
    rep(k,(int)cand.size()) if( cand[k] == line.p1 ) {
      int pos = k;
      while( pos-1 >= 0 && inPolygon(poly,(line.p1+cand[pos-1])/2.0) ) line.p1 = cand[--pos];
      break;
    }
 
    rep(k,(int)cand.size()) if( cand[k] == line.p2 ) {
      int pos = k;
      while( pos+1 < cand.size() && inPolygon(poly,(line.p2+cand[pos+1])/2.0) ) line.p2 = cand[++pos];
      break;
    }

    bool failed = false;
    rep(k,N) {
      if( onSegment(line.p1,line.p2,segs[k].p1) || onSegment(line.p1,line.p2,segs[k].p2) ) continue;
      if( intersectSS(line,segs[k]) ) { 
        Point cp = crosspoint(line,segs[k]);
        if( cp == line.p1 || cp == line.p2 ) continue;
        failed = true; break; }
    }
    if( failed ) continue;
    if( !inPolygon(poly,line) ) continue;
    ans = max(ans,abs(line.p1-line.p2));
  }
  printf("%.12f\n",ans);
}
 
int main(){
  int CNT = 1;
  while( scanf("%d",&N), N ){
    rep(i,N) scanf("%lf %lf",&ps[i].x,&ps[i].y);
    cout << "Case " << CNT++ << ": ";
    compute();
  }
  return 0;
}
### Prompt

Your challenge is to write a CPP solution to 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<bits/stdc++.h>
 
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define EPS (1e-8)
#define COUNTER_CLOCKWISE 1
#define CLOCKWISE -1 
#define ONLINE_BACK 2
#define ONLINE_FRONT -2
#define ON_SEGMENT 0
#define equals(a,b) (fabs((a)-(b)) < EPS)
 
using namespace std;
 
const int IINF = INT_MAX;
 
// template - begin
 
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 a){return Point(a*x,a*y);}
  Point operator / (double a){return Point(x/a,y/a);}
  Point operator * (Point a){ return Point(x * a.x - y * a.y, x * a.y + y * a.x); }
 
  bool operator < (const Point& p) const{ return !equals(x,p.x)?x<p.x:y<p.y; }
  bool operator == (const Point& p)const{ return fabs(x-p.x) < EPS && fabs(y-p.y) < EPS; }
 
};
 
struct Segment{
  Point p1,p2;
  Segment(Point p1 = Point(),Point p2 = Point()):p1(p1),p2(p2){}
  bool operator == (const Segment& p)const { return ( ( p.p1 == p1 && p.p2 == p2 ) || ( p.p1 == p2 && p.p2 == p1 ) ); }
};
 
typedef Point Vector;
typedef Segment Line;
typedef vector<Point> Polygon;
 
ostream& operator << (ostream& os,const Point& a){ os << "(" << a.x << "," << a.y << ")"; }
 
ostream& operator << (ostream& os,const Segment& a){ os << "( " << a.p1 << " , " << a.p2 << " )"; }
 
double dot(Point a,Point b){ return a.x*b.x + a.y*b.y; }
 
double cross(Point a,Point b){ return a.x*b.y - a.y*b.x; }
 
double norm(Point a){ return a.x*a.x+a.y*a.y; }
 
double abs(Point a){ return sqrt(norm(a)); }
 
//rad は角度をラジアンで持たせること
Point rotate(Point a,double rad){ return Point(cos(rad)*a.x - sin(rad)*a.y,sin(rad)*a.x + cos(rad)*a.y); }
 
// 度をラジアンに変換
double toRad(double agl){ return agl*M_PI/180.0; }
 
// a => prev, b => cur, c=> next
// prev から cur へ行って next へ行く際の角度を求める
double getArg(Point a,Point b,Point c){
  double arg1 = atan2(b.y-a.y,b.x-a.x);
  double arg2 = atan2(c.y-b.y,c.x-b.x);
  double arg = fabs( arg1 - arg2 );
  while( arg > M_PI ) arg -= 2.0 * M_PI;
  return fabs(arg);
}
 
// template - end
 
// ccw - begin
 
int ccw(Point p0,Point p1,Point p2){
  Point a = p1-p0;
  Point b = p2-p0;
  if(cross(a,b) > EPS)return COUNTER_CLOCKWISE;
  if(cross(a,b) < -EPS)return CLOCKWISE;
  if(dot(a,b) < -EPS)return ONLINE_BACK;
  if(norm(a) < norm(b))return ONLINE_FRONT;
  return ON_SEGMENT;
}
 
// ccw - end
 
// intersect - begin
 
bool intersectLL(Line l, Line m) {
  return abs(cross(l.p2-l.p1, m.p2-m.p1)) > EPS || // non-parallel
         abs(cross(l.p2-l.p1, m.p1-l.p1)) < EPS;   // same line
}
bool intersectLS(Line l, Line s) {
  return cross(l.p2-l.p1, s.p1-l.p1)*       // s[0] is left of l
         cross(l.p2-l.p1, s.p2-l.p1) < EPS; // s[1] is right of l
}
bool intersectLP(Line l,Point p) {
  return abs(cross(l.p2-p, l.p1-p)) < EPS;
}
bool intersectSS(Line s, Line t) {
  return ccw(s.p1,s.p2,t.p1)*ccw(s.p1,s.p2,t.p2) <= 0 &&
         ccw(t.p1,t.p2,s.p1)*ccw(t.p1,t.p2,s.p2) <= 0;
}
bool intersectSP(Line s, Point p) {
  return abs(s.p1-p)+abs(s.p2-p)-abs(s.p2-s.p1) < EPS; // triangle inequality
}
 
Point projection(Line l,Point p) {
  double t = dot(p-l.p1, l.p1-l.p2) / norm(l.p1-l.p2);
  return l.p1 + (l.p1-l.p2)*t;
}
Point reflection(Line l,Point p) {
  return p + (projection(l, p) - p) * 2;
}
double distanceLP(Line l, Point p) {
  return abs(p - projection(l, p));
}
double distanceLL(Line l, Line m) {
  return intersectLL(l, m) ? 0 : distanceLP(l, m.p1);
}
 
double distanceLS(Line l, Line s) {
  if (intersectLS(l, s)) return 0;
  return min(distanceLP(l, s.p1), distanceLP(l, s.p2));
}
double distanceSP(Line s, Point p) {
  Point r = projection(s, p);
  if (intersectSP(s, r)) return abs(r - p);
  return min(abs(s.p1 - p), abs(s.p2 - p));
}
 
double distanceSS(Line s, Line t) {
  if (intersectSS(s, t)) return 0;
  return min(min(distanceSP(s, t.p1), distanceSP(s, t.p2)),
             min(distanceSP(t, s.p1), distanceSP(t, s.p2)));
}
 
Point crosspoint(Line l,Line m){
  double A = cross(l.p2-l.p1,m.p2-m.p1);
  double B = cross(l.p2-l.p1,l.p2-m.p1);
  if(abs(A) < EPS && abs(B) < EPS){
    vector<Point> vec;
    vec.push_back(l.p1),vec.push_back(l.p2),vec.push_back(m.p1),vec.push_back(m.p2);
    sort(vec.begin(),vec.end());
    assert(vec[1] == vec[2]);
    return vec[1];
    //return m.p1;
  }
  if(abs(A) < EPS)assert(false);
  return m.p1 + (m.p2-m.p1)*(B/A);
}
 
 
// intersect - end
 

// onSegment - being
 
//cross product of pq and pr

double cross3p(Point p,Point q,Point r) { return (r.x-q.x) * (p.y -q.y) - (r.y - q.y) * (p.x - q.x); }
   
//returns true if point r is on the same line as the line pq
bool collinear(Point p,Point q,Point r){ return fabs(cross3p(p,q,r)) < EPS; }
   
//returns true if point t is on the left side of line pq
bool ccwtest(Point p,Point q,Point r){ return cross3p(p,q,r) > 0; }
  
bool onSegment(Point p,Point q,Point r){
  return collinear(p,q,r) && equals(sqrt(pow(p.x-r.x,2)+pow(p.y-r.y,2)) + sqrt(pow(r.x-q.x,2) + pow(r.y-q.y,2) ),sqrt(pow(p.x-q.x,2)+pow(p.y-q.y,2)) ) ;
}

double angle(Point a,Point b,Point c){
  double ux = b.x - a.x, uy = b.y - a.y;
  double vx = c.x - a.x, vy = c.y - a.y;
  return acos((ux*vx + uy*vy)/sqrt((ux*ux + uy*uy) * (vx*vx + vy*vy)));
}  
   
//多角形poly内（線分上も含む）に点pが存在するかどうは判定する  
bool inPolygon(Polygon poly,Point p){
  if((int)poly.size() == 0)return false;

  rep(i,poly.size())
    if(onSegment(poly[i],poly[(i+1)%poly.size()],p))return true;

  double sum = 0;
  for(int i=0; i < (int)poly.size() ;i++){
    if( equals(cross(poly[i]-p,poly[(i+1)%poly.size()]-p),0.0) ) continue; // ３点が平行だとangleがnanを返しsumがnanになり死ぬ
      if( cross3p(p,poly[i],poly[(i+1)%poly.size()]) < 0)
        sum -= angle(p,poly[i],poly[(i+1)%poly.size()]);
      else
        sum += angle(p,poly[i],poly[(i+1)%poly.size()]);
    }
  return (fabs(sum - 2*M_PI) < EPS || fabs(sum + 2*M_PI) < EPS);
}  
 
 
// onSegment - end
 
bool inPolygon(const Polygon &poly,Segment seg){
  vector<Point> vp;
  vp.push_back(seg.p1);
  vp.push_back(seg.p2);
  rep(i,(int)poly.size()) {
    Segment edge = Segment(poly[i],poly[(i+1)%(int)poly.size()]);
    if( equals(cross(seg.p1-edge.p1,seg.p2-edge.p2),0.0) ) {
      if( onSegment(seg.p1,seg.p2,edge.p1) ) vp.push_back(edge.p1);
      if( onSegment(seg.p1,seg.p2,edge.p2) ) vp.push_back(edge.p2);
    } else {
      if( intersectSS(seg,edge) ) vp.push_back(crosspoint(seg,edge));
    }
  }
  sort(vp.begin(),vp.end());
  vp.erase(unique(vp.begin(),vp.end()),vp.end());
  rep(i,(int)vp.size()-1) {
    Point middle_point = ( vp[i] + vp[i+1] ) / 2.0;
    if( !inPolygon(poly,middle_point) ) return false;
  }
  return true;  
}
 
 
const int MAX_N = 110;
int N;
Point ps[MAX_N];
 
bool LTE(double a,double b) { return equals(a,b) || a < b ; } 
 
void compute(){
 
  vector<Point> poly;
  rep(i,N) poly.push_back(ps[i]);
  vector<Segment> segs;
  rep(i,N) segs.push_back(Segment(ps[i],ps[(i+1)%N]));
 
  double ans = 0;
  rep(i,N) REP(j,i+1,N) {

    Line line = Line(ps[i],ps[j]);

    vector<Point> cand;
    cand.push_back(line.p1);
    cand.push_back(line.p2);
    rep(k,N) {
      Segment seg = Segment(ps[k],ps[(k+1)%N]);
      if( !( line == seg ) && intersectLS(line,seg) && !equals(cross(line.p1-line.p2,seg.p1-seg.p2),0.0) ) cand.push_back(crosspoint(line,seg));
    }
    sort(cand.begin(),cand.end());
    cand.erase(unique(cand.begin(),cand.end()),cand.end());

    line.p1 = ps[i], line.p2 = ps[j];
    rep(k,(int)cand.size()) if( cand[k] == line.p1 ) {
      int pos = k;
      while( pos-1 >= 0 && inPolygon(poly,(line.p1+cand[pos-1])/2.0) ) line.p1 = cand[--pos];
      break;
    }
 
    rep(k,(int)cand.size()) if( cand[k] == line.p2 ) {
      int pos = k;
      while( pos+1 < cand.size() && inPolygon(poly,(line.p2+cand[pos+1])/2.0) ) line.p2 = cand[++pos];
      break;
    }

    bool failed = false;
    rep(k,N) {
      if( onSegment(line.p1,line.p2,segs[k].p1) || onSegment(line.p1,line.p2,segs[k].p2) ) continue;
      if( intersectSS(line,segs[k]) ) { 
        Point cp = crosspoint(line,segs[k]);
        if( cp == line.p1 || cp == line.p2 ) continue;
        failed = true; break; }
    }
    if( failed ) continue;
    if( !inPolygon(poly,line) ) continue;
    ans = max(ans,abs(line.p1-line.p2));
  }
  printf("%.12f\n",ans);
}
 
int main(){
  int CNT = 1;
  while( scanf("%d",&N), N ){
    rep(i,N) scanf("%lf %lf",&ps[i].x,&ps[i].y);
    cout << "Case " << CNT++ << ": ";
    compute();
  }
  return 0;
}
```