#include<cmath>
#include<queue>
#include<cstdio>
#include<algorithm>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

const long double EPS=1e-7;
const long double INF=1e77;
const long double PI=acos(-1);

struct point{
	long double x,y;
	point():x(0),y(0){}
	point(long double x,long double y):x(x),y(y){}
	point &operator/=(long double c){ x/=c; y/=c; return *this; }
	point operator+(const point &a)const{ return point(x+a.x,y+a.y); }
	point operator-(const point &a)const{ return point(x-a.x,y-a.y); }
	bool operator< (const point &a)const{ return x+EPS<a.x || abs(x-a.x)<EPS && y+EPS<a.y; }
	bool operator==(const point &a)const{ return abs(x-a.x)<EPS && abs(y-a.y)<EPS; }
};

point operator*(long double c,const point &a){ return point(c*a.x,c*a.y); }

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

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

long double abs(const point &a){ return sqrt(a.x*a.x+a.y*a.y); }

long double abs2(const point &a){ return a.x*a.x+a.y*a.y; }

point rot(const point &a,long double theta){ return point(a.x*cos(theta)-a.y*sin(theta),a.x*sin(theta)+a.y*cos(theta)); }

struct line{
	point a,b;
	line(){}
	line(const point &a,const point &b):a(a),b(b){}
};

struct segment{
	point a,b;
	segment(){}
	segment(const point &a,const point &b):a(a),b(b){}
	operator line()const{ return line(a,b); }
};

point proj(const line &L,const point &p){ return L.a+dot(p-L.a,L.b-L.a)/abs2(L.b-L.a)*(L.b-L.a); }

enum{CCW=1,CW=-1,ON=0};
int ccw(const point &a,const point &b,const point &c){
	long double rdir=cross(b-a,c-a);
	if(rdir> EPS) return CCW;
	if(rdir<-EPS) return CW;
	return ON;
}

bool cover(const segment &S,const point &p){
	return abs(cross(S.a-p,S.b-p))<EPS && dot(S.a-p,S.b-p)<EPS;
}

bool intersect(const segment &S1,const segment &S2){
	if(max(S1.a.x,S1.b.x)+EPS<min(S2.a.x,S2.b.x)
	|| max(S1.a.y,S1.b.y)+EPS<min(S2.a.y,S2.b.y)
	|| max(S2.a.x,S2.b.x)+EPS<min(S1.a.x,S1.b.x)
	|| max(S2.a.y,S2.b.y)+EPS<min(S1.a.y,S1.b.y)) return false;
	return ccw(S1.a,S1.b,S2.a)*ccw(S1.a,S1.b,S2.b)<=0
		&& ccw(S2.a,S2.b,S1.a)*ccw(S2.a,S2.b,S1.b)<=0;
}

point get_intersect(const segment &S1,const segment &S2){
	long double a1=cross(S1.b-S1.a,S2.b-S2.a);
	long double a2=cross(S1.b-S1.a,S1.b-S2.a);
	if(abs(a1)<EPS){
		if(cover(S1,S2.a)) return S2.a;
		if(cover(S1,S2.b)) return S2.b;
		if(cover(S2,S1.a)) return S1.a;
		return S1.b;
	}
	return S2.a+a2/a1*(S2.b-S2.a);
}

void arrangement(const vector<segment> &S,vector<point> &P,vector<int> *G,point s,point g){
	int n=S.size();
	P.clear();
	P.push_back(s); // テァツ可ケテ・ツ按・テ」ツ?ォティツソツステ・ツ環?」ツ?凖」ツつ?
	P.push_back(g); // テァツ可ケテ・ツ按・テ」ツ?ォティツソツステ・ツ環?」ツ?凖」ツつ?
	rep(i,n){
		P.push_back(S[i].a);
		P.push_back(S[i].b);
		rep(j,i) if(intersect(S[i],S[j])) P.push_back(get_intersect(S[i],S[j]));
	}
	sort(P.begin(),P.end());
	P.erase(unique(P.begin(),P.end()),P.end());

	rep(u,P.size()) G[u].clear();
	rep(i,n){
		vector<int> on;
		rep(u,P.size()) if(cover(S[i],P[u])) on.push_back(u);
		rep(j,(int)on.size()-1){
			int u=on[j],v=on[j+1];
			G[u].push_back(v);
			G[v].push_back(u);
		}
	}
}

int main(){
	for(int cas=1,n;scanf("%d",&n),n;cas++){
		point s,g; scanf("%Lf%Lf%Lf%Lf",&s.x,&s.y,&g.x,&g.y);
		segment F[100];
		rep(i,n) scanf("%Lf%Lf%Lf%Lf",&F[i].a.x,&F[i].a.y,&F[i].b.x,&F[i].b.y);

		vector<segment> S;
		rep(i,n){
			point v=rot(F[i].b-F[i].a,PI/2); v/=abs(v);
			// start-electrode, goal-electrode
			if(cover(F[i],proj(F[i],s))) S.push_back(segment(s-1e4*v,s+1e4*v));
			if(cover(F[i],proj(F[i],g))) S.push_back(segment(g-1e4*v,g+1e4*v));
			// electrode rail
			S.push_back(segment(F[i].a-1e4*v,F[i].a+1e4*v));
			S.push_back(segment(F[i].b-1e4*v,F[i].b+1e4*v));
		}

		vector<point> P;
		static vector<int> G[50000];
		arrangement(S,P,G,s,g);

		int s_id=-1,g_id=-1;
		rep(u,P.size()){
			if(P[u]==s) s_id=u;
			if(P[u]==g) g_id=u;
		}

		// Dijkstra
		vector<long double> d(P.size(),INF);
		d[s_id]=0;
		priority_queue< pair<long double,int> > Q; Q.push(make_pair(0,s_id));
		while(!Q.empty()){
			long double d_now=-Q.top().first;
			int u=Q.top().second; Q.pop();

			if(d[u]<d_now-EPS) continue;

			rep(i,G[u].size()){
				int v=G[u][i];
				long double d_next=d[u]+abs(P[u]-P[v]);
				if(d_next+EPS<d[v]){
					d[v]=d_next;
					Q.push(make_pair(-d[v],v));
				}
			}
		}

		printf("Case %d: ",cas);
		if(d[g_id]<INF/2) printf("%.5Lf\n",d[g_id]); else puts("Impossible");
	}

	return 0;
}
### Prompt

Please create a solution in Cpp to the following 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

### Response

```cpp
#include<cmath>
#include<queue>
#include<cstdio>
#include<algorithm>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

const long double EPS=1e-7;
const long double INF=1e77;
const long double PI=acos(-1);

struct point{
	long double x,y;
	point():x(0),y(0){}
	point(long double x,long double y):x(x),y(y){}
	point &operator/=(long double c){ x/=c; y/=c; return *this; }
	point operator+(const point &a)const{ return point(x+a.x,y+a.y); }
	point operator-(const point &a)const{ return point(x-a.x,y-a.y); }
	bool operator< (const point &a)const{ return x+EPS<a.x || abs(x-a.x)<EPS && y+EPS<a.y; }
	bool operator==(const point &a)const{ return abs(x-a.x)<EPS && abs(y-a.y)<EPS; }
};

point operator*(long double c,const point &a){ return point(c*a.x,c*a.y); }

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

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

long double abs(const point &a){ return sqrt(a.x*a.x+a.y*a.y); }

long double abs2(const point &a){ return a.x*a.x+a.y*a.y; }

point rot(const point &a,long double theta){ return point(a.x*cos(theta)-a.y*sin(theta),a.x*sin(theta)+a.y*cos(theta)); }

struct line{
	point a,b;
	line(){}
	line(const point &a,const point &b):a(a),b(b){}
};

struct segment{
	point a,b;
	segment(){}
	segment(const point &a,const point &b):a(a),b(b){}
	operator line()const{ return line(a,b); }
};

point proj(const line &L,const point &p){ return L.a+dot(p-L.a,L.b-L.a)/abs2(L.b-L.a)*(L.b-L.a); }

enum{CCW=1,CW=-1,ON=0};
int ccw(const point &a,const point &b,const point &c){
	long double rdir=cross(b-a,c-a);
	if(rdir> EPS) return CCW;
	if(rdir<-EPS) return CW;
	return ON;
}

bool cover(const segment &S,const point &p){
	return abs(cross(S.a-p,S.b-p))<EPS && dot(S.a-p,S.b-p)<EPS;
}

bool intersect(const segment &S1,const segment &S2){
	if(max(S1.a.x,S1.b.x)+EPS<min(S2.a.x,S2.b.x)
	|| max(S1.a.y,S1.b.y)+EPS<min(S2.a.y,S2.b.y)
	|| max(S2.a.x,S2.b.x)+EPS<min(S1.a.x,S1.b.x)
	|| max(S2.a.y,S2.b.y)+EPS<min(S1.a.y,S1.b.y)) return false;
	return ccw(S1.a,S1.b,S2.a)*ccw(S1.a,S1.b,S2.b)<=0
		&& ccw(S2.a,S2.b,S1.a)*ccw(S2.a,S2.b,S1.b)<=0;
}

point get_intersect(const segment &S1,const segment &S2){
	long double a1=cross(S1.b-S1.a,S2.b-S2.a);
	long double a2=cross(S1.b-S1.a,S1.b-S2.a);
	if(abs(a1)<EPS){
		if(cover(S1,S2.a)) return S2.a;
		if(cover(S1,S2.b)) return S2.b;
		if(cover(S2,S1.a)) return S1.a;
		return S1.b;
	}
	return S2.a+a2/a1*(S2.b-S2.a);
}

void arrangement(const vector<segment> &S,vector<point> &P,vector<int> *G,point s,point g){
	int n=S.size();
	P.clear();
	P.push_back(s); // テァツ可ケテ・ツ按・テ」ツ?ォティツソツステ・ツ環?」ツ?凖」ツつ?
	P.push_back(g); // テァツ可ケテ・ツ按・テ」ツ?ォティツソツステ・ツ環?」ツ?凖」ツつ?
	rep(i,n){
		P.push_back(S[i].a);
		P.push_back(S[i].b);
		rep(j,i) if(intersect(S[i],S[j])) P.push_back(get_intersect(S[i],S[j]));
	}
	sort(P.begin(),P.end());
	P.erase(unique(P.begin(),P.end()),P.end());

	rep(u,P.size()) G[u].clear();
	rep(i,n){
		vector<int> on;
		rep(u,P.size()) if(cover(S[i],P[u])) on.push_back(u);
		rep(j,(int)on.size()-1){
			int u=on[j],v=on[j+1];
			G[u].push_back(v);
			G[v].push_back(u);
		}
	}
}

int main(){
	for(int cas=1,n;scanf("%d",&n),n;cas++){
		point s,g; scanf("%Lf%Lf%Lf%Lf",&s.x,&s.y,&g.x,&g.y);
		segment F[100];
		rep(i,n) scanf("%Lf%Lf%Lf%Lf",&F[i].a.x,&F[i].a.y,&F[i].b.x,&F[i].b.y);

		vector<segment> S;
		rep(i,n){
			point v=rot(F[i].b-F[i].a,PI/2); v/=abs(v);
			// start-electrode, goal-electrode
			if(cover(F[i],proj(F[i],s))) S.push_back(segment(s-1e4*v,s+1e4*v));
			if(cover(F[i],proj(F[i],g))) S.push_back(segment(g-1e4*v,g+1e4*v));
			// electrode rail
			S.push_back(segment(F[i].a-1e4*v,F[i].a+1e4*v));
			S.push_back(segment(F[i].b-1e4*v,F[i].b+1e4*v));
		}

		vector<point> P;
		static vector<int> G[50000];
		arrangement(S,P,G,s,g);

		int s_id=-1,g_id=-1;
		rep(u,P.size()){
			if(P[u]==s) s_id=u;
			if(P[u]==g) g_id=u;
		}

		// Dijkstra
		vector<long double> d(P.size(),INF);
		d[s_id]=0;
		priority_queue< pair<long double,int> > Q; Q.push(make_pair(0,s_id));
		while(!Q.empty()){
			long double d_now=-Q.top().first;
			int u=Q.top().second; Q.pop();

			if(d[u]<d_now-EPS) continue;

			rep(i,G[u].size()){
				int v=G[u][i];
				long double d_next=d[u]+abs(P[u]-P[v]);
				if(d_next+EPS<d[v]){
					d[v]=d_next;
					Q.push(make_pair(-d[v],v));
				}
			}
		}

		printf("Case %d: ",cas);
		if(d[g_id]<INF/2) printf("%.5Lf\n",d[g_id]); else puts("Impossible");
	}

	return 0;
}
```