Problem: Scientist Frank, majoring in electrochemistry, has developed line-shaped strange electrodes called F-electrodes. During being activated, each F-electrode causes a special potential on and between the two lines touching the F-electrode’s endpoints at a right angle. Then electrically-charged particles located inside the potential area get to move in the direction parallel to the potential boundary (i.e. perpendicular to the F-electrode), either toward or against F-electrode. The moving direction can be easily controlled between the two possibles; it is also possible to get particles to pass through F-electrodes. In addition, unlike ordinary electrodes, F-electrodes can affect particles even infinitely far away, as long as those particles are located inside the potential area. On the other hand, two different F-electrodes cannot be activated at a time, since their potentials conflict strongly.

We can move particles on our will by controlling F-electrodes. However, in some cases, we cannot lead them to the desired positions due to the potential areas being limited. To evaluate usefulness of F-electrodes from some aspect, Frank has asked you the following task: to write a program that finds the shortest distances from the particles’ initial positions to their destinations with the given sets of F-electrodes.

<image>



Input

The input consists of multiple test cases. The first line of each case contains N (1 ≤ N ≤ 100) which represents the number of F-electrodes. The second line contains four integers xs, ys, xt and yt, where (xs, ys) and (xt, yt) indicate the particle’s initial position and destination. Then the description of N F-electrodes follow. Each line contains four integers Fxs, Fys, Fxt and Fyt, where (Fxs, Fys) and (Fxt, Fyt ) indicate the two endpoints of an F-electrode. All coordinate values range from 0 to 100 inclusive.

The input is terminated by a case with N = 0.

Output

Your program must output the case number followed by the shortest distance between the initial position to the destination. Output “Impossible” (without quotes) as the distance if it is impossible to lead the elementary particle to the destination. Your answers must be printed with five digits after the decimal point. No absolute error in your answers may exceed 10-5.

Example

Input

2
2 1 2 2
0 0 1 0
0 1 0 2
0


Output

Case 1: 3.00000

Solution (in CPP):

Solution:
#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>
#include<cassert>
#include<iomanip>
#include<complex>
#include<queue>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define inf (1<<29)
#define EPS (1e-8)
#define all(n) (n).begin(),(n).end()
#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;

//*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-

class Point
{
  public:
  double x,y;

  Point(double x = -inf,double y = -inf): 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);}

  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(-inf,-inf),Point p2 = Point(-inf,-inf)):p1(p1),p2(p2){}
  bool operator == (const Segment& p)const
  {
    return p.p1 == p1 && p.p2 == p2;
  }
};

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; }

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;
}

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) return m.p1; // same line
  if (abs(A) < EPS) assert(false); // !!!PRECONDITION NOT SATISFIED!!!
  return m.p1 +   (m.p2 - m.p1) * (B / A);
}



// -*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-|

struct SP
{
  Segment seg;
  int type;// type 0 -> Point, type 1 -> Segment;
  SP(Segment seg = Segment(),int type=inf):seg(seg),type(type){}
};

struct Edge
{
  int from,to;
  double cost;
  Edge(int from=inf,int to=inf,double cost=inf):from(from),to(to),cost(cost){}
  bool operator < (const Edge& a)const
  {
    return cost < a.cost;
  }
};

typedef vector<Edge> vE;
typedef vector<vE> vvE;

int N;
vector<SP> vec;


vector<vector<Edge> > segmentArrangementVer1(vector<Segment> vs,vector<Point> &ps)
{

  rep(i,vs.size())
    REP(j,i+1,vs.size())
      if(intersectSS(vs[i],vs[j]))
        ps.push_back(Point(crosspoint(vs[i],vs[j])));

  //
  ps.push_back(vec[0].seg.p1);
  ps.push_back(vec[1].seg.p2);
  //

  sort(all(ps));  
  ps.erase(unique(all(ps)),ps.end());

  vector<vector<Edge> > ret(ps.size());

  for(int i=0;i<vs.size();i++)
    {
      vector<pair<double,int> > list;
      rep(j,ps.size())
	if(intersectSP(vs[i],ps[j]))
	  list.push_back(pair<double,int>(norm(vs[i].p1-ps[j]),j));

      sort(all(list));

      //for(int j=0;j<list.size()-1;++j) is not good -> テ」ツつサテ」ツつーテ」ツつ?
      for(int j=0;j+1<list.size();++j)
	{
	  int from = list[j].second, to = list[j+1].second;
	  double cost = abs(ps[from]-ps[to]);
	  ret[from].push_back(Edge(from,to,cost));
	  ret[to].push_back(Edge(to,from,cost));
	}
    }  
  return ret;
}

void toSegOnly(vector<Segment> &vs)
{
  rep(i,2)
    {
      REP(j,2,2+N)
	{
	  assert(vec[i].seg.p1 == vec[i].seg.p2);
	  Point prj = projection(vec[j].seg,vec[i].seg.p1);
	  if(intersectSP(vec[j].seg,prj))
	    {
	      if(vec[i].seg.p1 == prj)continue;
	      Point e = vec[i].seg.p1 - prj;
	      e = (e/abs(e))*1000;//100000テ」ツ?ィテ」ツ?凝」ツ?ォテ」ツ?凖」ツつ凝」ツ?ィティツェツ、テ・ツキツョテ」ツ?ァdeath
	      vs.push_back(Segment(vec[i].seg.p1-e,prj+e));
	    }
	}
    }

  REP(j,2,2+N)
    {
      Segment seg = Segment(vec[j].seg.p1 - vec[j].seg.p2,vec[j].seg.p2 - vec[j].seg.p2);
      Point rig = rotate(seg.p1,toRad(90.0));
      rig = (rig/abs(rig))*1000;
      vs.push_back(Segment(vec[j].seg.p1-rig,vec[j].seg.p1+rig));
      vs.push_back(Segment(vec[j].seg.p2-rig,vec[j].seg.p2+rig));
    }
}

//segment merge--------
bool merge_if_able(Segment &s, Segment t) {
  if (abs(cross(s.p2-s.p1, t.p2-t.p1)) > EPS) return false;
  if (ccw(s.p1, t.p1, s.p2) == +1 ||
      ccw(s.p1, t.p1, s.p2) == -1) return false; // not on the same line
  if (ccw(s.p1, s.p2, t.p1) == -2 ||
      ccw(t.p1, t.p2, s.p1) == -2) return false; // separated
  s = Segment(min(s.p1, t.p1), max(s.p2, t.p2));
  return true;
}
void merge_segments(vector<Segment>& segs) {
  for (int i = 0; i < segs.size(); ++i)
    if (segs[i].p2 < segs[i].p1)
      swap(segs[i].p2, segs[i].p1);
  for (int i = 0; i < segs.size(); ++i)
    for (int j = i+1; j < segs.size(); ++j)
      if (merge_if_able(segs[i], segs[j]))
        segs[j--] = segs.back(), segs.pop_back();
}
// -------------------

struct Pox
{
  int cur;
  double cost;
  Pox(int cur=inf,double cost=inf):cur(cur),cost(cost){}
  bool operator < (const Pox& a)const
  {
    return cost > a.cost;
  }
};

void dijkstra(vvE &G,int st,int ed)
{
  int n = G.size();
  double mincost[n];
  rep(i,n)mincost[i] = inf;
  mincost[st] = 0;
  priority_queue<Pox> Q;
  Q.push(Pox(st,0));

  while(!Q.empty())
    {
      Pox pox = Q.top(); Q.pop();

      if(pox.cur == ed)
	{
	  cout << setiosflags(ios::fixed) << setprecision(5) << pox.cost << endl;
	  return;
	}

      rep(i,G[pox.cur].size())
	{
	  int next = G[pox.cur][i].to;
	  double cost = G[pox.cur][i].cost;
	  if(!equals(mincost[next],pox.cost+cost) && mincost[next] > pox.cost + cost)
	    {
	      mincost[next] = pox.cost + cost;
	      Q.push(Pox(next,pox.cost+cost));
	    }
	}

    }
  cout << "Impossible" << endl;
}

void compute()
{
  vector<Segment> vs;
  toSegOnly(vs);

  merge_segments(vs);  

  vector<Point> ps;
  vvE G = segmentArrangementVer1(vs,ps);

  int st_index,ed_index;
  rep(i,ps.size())
    {
      if(ps[i] == vec[0].seg.p1)st_index = i;
      if(ps[i] == vec[1].seg.p1)ed_index = i;
    }

  dijkstra(G,st_index,ed_index);
   
}

int main()
{
  int CNT = 1;
  while(cin >> N,N)
    {
      vec.clear();
      vec.resize(N+2);
      double x,y;
      rep(i,2)
	{
	  cin >> x >> y;
	  vec[i].seg.p1 = vec[i].seg.p2 = Point(x,y);
	  vec[i].type = 0;
	}
      rep(i,N)
	cin >> vec[2+i].seg.p1.x >> vec[2+i].seg.p1.y >> vec[2+i].seg.p2.x >> vec[2+i].seg.p2.y;
      cout << "Case " << CNT++ << ": ";
      compute();
    }
  return 0;
}