Problem: Hide-and-seek is a children’s game. Players hide here and there, and one player called it tries to find all the other players.

Now you played it and found all the players, so it’s turn to hide from it. Since you have got tired of running around for finding players, you don’t want to play it again. So you are going to hide yourself at the place as far as possible from it. But where is that?

Your task is to find the place and calculate the maximum possible distance from it to the place to hide.



Input

The input contains a number of test cases.

The first line of each test case contains a positive integer N (N ≤ 1000). The following N lines give the map where hide-and-seek is played. The map consists of N corridors. Each line contains four real numbers x1, y1, x2, and y2, where (x1, y1 ) and (x2, y2 ) indicate the two end points of the corridor. All corridors are straight, and their widths are negligible. After these N lines, there is a line containing two real numbers sx and sy, indicating the position of it. You can hide at an arbitrary place of any corridor, and it always walks along corridors. Numbers in the same line are separated by a single space.

It is guaranteed that its starting position (sx, sy) is located on some corridor and linked to all corridors directly or indirectly.

The end of the input is indicated by a line containing a single zero.

Output

For each test case, output a line containing the distance along the corridors from ‘it”s starting position to the farthest position. The value may contain an error less than or equal to 0.001. You may print any number of digits below the decimal point.

Example

Input

2
0 0 3 3
0 4 3 1
1 1
0


Output

4.243

Solution (in CPP):

Solution:
#include<complex>
#include<vector>
#include<iostream>
#include<stack>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<algorithm>

#define FRONT 0x01
#define RIGHT 0x02
#define BACK 0x04
#define LEFT 0x08
#define OVER 0x10

#define sc second
#define fr first

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

using namespace std;

typedef double elem;
typedef complex<elem> point, vec;
typedef pair<point, point> line, seg, pp;

const double eps = 1.0e-8;
const double pi = acos(-1.0);
const double inf = 1e40;
point base(0,0);

// lZ
inline elem sq(elem a){ return a*a; }
inline elem cq(elem a){ return a*a*a; }

// pxÏ·
elem rad(elem deg){ return (deg/180)*pi; }
elem deg(elem rad){ return (rad*180)/pi; }

// ®¬_Ìô¢AÈÇ
bool eq(elem a, elem b){ return abs(a-b) < eps; }
bool lt(elem a, elem b){ return !eq(a,b) && a < b; }
bool leq(elem a, elem b){ return eq(a,b) || a < b; }
bool gt(elem a, elem b){ return !eq(a,b) && a > b; }
bool geq(elem a, elem b){ return eq(a,b) || a > b; }
bool ltz(elem a){ return lt( a, 0 ); }
bool gtz(elem a){ return gt( a, 0 ); }
bool eqv(vec a, vec b){ return eq( abs(b-a),0); }
bool is_zv(vec v){ return eq(abs(v),0); }
elem emax(elem a, elem b){ return gt(a,b)?a:b; }
elem emin(elem a, elem b){ return lt(a,b)?a:b; }

// _Iy[^
bool far(point a, point b){ return gtz( abs(b-a) ); }
bool near(point a, point b){ return leq( abs(b-a), 0 ); }
elem dot(vec a, vec b){ return (a.real() * b.real() + a.imag() * b.imag() ); }
elem cross(vec a, vec b){ return ( a.real() * b.imag() - a.imag() * b.real() ); }

// a©çbÜÅvñèÌpxAàpA]ñ]
elem varg(vec a, vec b){
  elem ret=arg(a)-arg(b);
  if(lt(ret,0))ret+=2*pi;
  if(gt(ret,2*pi))ret-=2*pi;
  if(eq(ret,2*pi))ret=0;
  return ret;
}
elem arg(vec a, vec b){ return acos( dot(a,b) / ( abs(a) * abs(b) ) ); }
point rot(point p, elem theta){ return p * polar((elem)1.0, theta); }
point rotdeg(point p, elem deg){ return p * polar((elem)1.0, rad(deg)); }

// ñ_Ô£A¼üÆ_ÌÅZ£AüªÆ_ÌÅZ£
elem dist(point a, point b){ return abs(a-b); }
elem dist_l(line l, point x){ return abs(cross(l.sc-l.fr,x-l.fr)) / abs(l.sc-l.fr); }
elem dist_seg(seg s, point x)
{
  if( ltz( dot(s.sc-s.fr,x-s.fr) ) ) return abs(x-s.fr);
  if( ltz( dot(s.fr-s.sc,x-s.sc) ) ) return abs(x-s.sc);
  return dist_l(s,x);
}

// PÊxNgA@üxNgAPÊ@üxNg
vec uvec(vec a){ return a / abs(a); }
vec nmr(vec a){ return a * vec(0,-1); }
vec nml(vec a){ return a * vec(0,1); }
vec unmr(vec a){ return uvec( nmr(a) ); }
vec unml(vec a){ return uvec( nml(a) ); }

// ¼ðA½s»è
bool orth(point a1, point a2, point b1, point b2){ return eq( dot( a2 - a1, b2 - b1 ), 0 ); }
bool orth(vec v1, vec v2){ return eq( dot(v1, v2), 0 ); }
bool prll(point a1, point a2, point b1, point b2){ return eq( cross( a2 - a1, b2 - b1 ), 0 ); }
bool prll(vec v1, vec v2){ return eq( cross(v1, v2), 0 ); }

// CCW oXg¾ªA¸xÉæé
int ccw(point a, point b, point x){
  b -= a;
  x -= a;
  // if( is_zv(b) || is_zv( x ) ) return ERROR;
  if( gtz( cross(b,x) ) ) return LEFT;
  if( ltz( cross(b,x) ) ) return RIGHT;
  if( ltz( dot(b,x) ) ) return BACK;
  if( abs(b) < abs(x) ) return FRONT;
  return OVER;
}

bool intersected_seg(seg a, seg b)
{
  if( ccw(a.fr,a.sc,b.fr)&OVER || ccw(a.fr,a.sc,b.sc)&OVER ) return true;
  return
    ( ccw(a.fr,a.sc,b.fr) | ccw(a.fr,a.sc,b.sc) ) == (LEFT|RIGHT) &&
    ( ccw(b.fr,b.sc,a.fr) | ccw(b.fr,b.sc,a.sc) ) == (LEFT|RIGHT) ;
}
bool intersected_l(line a, line b){
  return !prll(a.fr,a.sc,b.fr,b.sc);
}
point intersection_seg(seg a, seg b)
{
  elem d1 = dist_l(b,a.fr);
  elem d2 = dist_l(b,a.sc);
  return a.fr + ( d1 / (d1 + d2 ) ) * (a.sc-a.fr);
}
point intersection_l(line a, line b)
{
  vec va = a.sc - a.fr;
  vec vb = b.sc - b.fr;
  return a.fr + va * ( cross(vb, b.fr - a.fr) / cross(vb,va) );
}
bool intersection_seg(seg a, seg b, point &ret){
  if( intersected_seg(a,b) ){
    ret = intersection_seg(a,b);
    return true;
  }
  return false;
}
bool intersection_l(line a, line b, point &ret){
  if( intersected_l( a, b ) ){
    ret = intersection_l( a, b );
    return true;
  }
  return false;
}
bool intersection_lseg(line l, seg s, point &ret){
  point tmp;
  if( intersection_l(l,s,tmp) ){
    if(ccw(s.fr,s.sc,tmp)&OVER){
      ret=tmp;
      return true;
    }
  }
  return false;
}

struct Point{
  point p;
  Point():p(0,0){}
  Point(point tp):p(tp){}
  bool operator<(const Point &t)const{
    if(lt(p.real(),t.p.real()))return true;
    if(eq(p.real(),t.p.real())) return lt(p.imag(),t.p.imag());
    return false;
  }
};

struct Node{
  point p;
  set<int> line_id;
  Node(){}
};

struct Seg{
  seg s;
  vector<int> con;
  Seg(){}
  Seg( seg s ): s(s){}
};

typedef vector<Node> Graph;

struct State{
  int now;
  double cost;
  bool operator>(const State &t)const{
    return cost > t.cost;
  }
};

double dijkstra(vector<Seg> &segs, Graph &G, int s){
  double ret =0;
  
  priority_queue< State,vector<State>,greater<State> > pq;
  bool vis[G.size()];
  int pre[G.size()];
  double A[G.size()];

  for(int i = 0; i < G.size(); ++i){
    vis[i]=false;
    A[i]=inf;
    pre[i]=-1;
  }
  
  State init;
  init.now = s;
  init.cost = 0;
  A[s]=0;
  pq.push(init);
  while(!pq.empty()){
    State st_now = pq.top();
    pq.pop();
    int nowid = st_now.now;

    if( vis[nowid] ){
      continue;
    }else{
      vis[nowid]=true;
    }
    
    // cout << vis.size() << endl;
    // cout << "ID : " << st_now.now << ' ' << " POINT : " << G[st_now.now].p << " COST : " << st_now.cost << endl;

    for(set<int>::iterator its = G[nowid].line_id.begin(); its != G[nowid].line_id.end(); ++its){
      int segid = *its;
      for(int i = 0; i < segs[segid].con.size(); ++i){
	int nextid = segs[segid].con[i];
	double nextcost = st_now.cost + abs(G[nextid].p-G[nowid].p);
	Point np = Point( G[nextid].p );

	if( A[nextid] > nextcost ){
	  A[nextid]=nextcost;
	  pre[nextid]=nowid;
	  State nextState;
	  nextState.now = nextid;
	  nextState.cost = nextcost;
	  if( !vis[nextid] )
	    pq.push(nextState);
	}
      }
    }
  }
  
  vector<int> lid;
  for(int i = 0; i < G.size(); ++i){
    ret = max(ret,A[i]);
  }
  for(int i = 0; i < G.size(); ++i){
    if( i == G.size()-1 ) break;
    lid.push_back( i );
  }
  
  for(int i = 0; i < lid.size(); ++i){
    int nowid = lid[i];
    int preid = pre[nowid];
    int b = nowid;
    set<int> aid;
    for(set<int>::iterator its = G[nowid].line_id.begin(); its != G[nowid].line_id.end(); ++its){
      int segid = *its;
      int aleft=-1;
      int aright=-1;
      int afront=-1;
      double dleft=inf;
      double dright=inf;
      double dfront=inf;
      
      for(int i = 0; i < segs[segid].con.size(); ++i){
	int nextid = segs[segid].con[i];
	if( nowid == nextid ) continue;
	if( preid == nextid ) continue;
	
	double D = abs(G[nowid].p-G[nextid].p);
	int cw = ccw(G[preid].p,G[nowid].p,G[nextid].p);

	if( cw & LEFT ){
	  if( dleft > D ){
	    dleft = D;
	    aleft = nextid;
	  }
	}else if( cw & RIGHT ){
	  if( dright > D ){
	    dright = D;
	    aright = nextid;
	  }
	}else if( cw &(FRONT|OVER) ){
	  if( dfront > D ){
	    dfront = D;
	    afront = nextid;
	  }
	}
      }
      
      if( aleft>=0&& pre[aleft]!=nowid)aid.insert(aleft);
      if(aright>=0&&pre[aright]!=nowid)aid.insert(aright);
      if(afront>=0&&pre[afront]!=nowid)aid.insert(afront);
    }
    
    //cout << "B : " << b << endl;
    for(set<int>::iterator its = aid.begin(); its != aid.end(); ++its){
      //cout << *its << endl;
      if( leq( A[*its], A[b] ) ){
	elem dab = abs( G[*its].p - G[b].p );
	if( leq( A[*its], dab + A[b] ) ){
	  double t = (abs(A[b] - A[*its]) + dab ) / 2.;
	  ret = max(ret,t+A[*its]);
	}
      }
    }
    
  }
  return ret;
}

int main()
{
  while(true){
    int N;
    double ans;
    int id = 0;
    vector<Seg> corridor;
    map<Point,int> interid;
    Graph G;
    
    cin >> N;
    if( N == 0 ) break;
    for(int i = 0; i < N; ++i){
      elem x1,y1,x2,y2;
      cin >> x1 >> y1 >> x2 >> y2;
      corridor.push_back( Seg(seg( point(x1,y1), point(x2,y2) )) );
    }
    
    G.resize( N*N+2*N );
    id = 0;
    
    for(int i = 0; i < corridor.size(); ++i){

      int fid;
      int sid;
      Point pf = Point(corridor[i].s.first);
      Point ps = Point(corridor[i].s.second);

      if( interid.find( pf ) == interid.end() ){
	interid[ Point(corridor[i].s.first) ] = id;
	fid=id;
	++id;
      }else fid=interid[Point(corridor[i].s.first)];
      if( interid.find( ps ) == interid.end() ){
	interid[ Point(corridor[i].s.second ) ] = id;
	sid=id;
	++id;
      }else sid=interid[Point(corridor[i].s.second)];
      
      corridor[i].con.push_back( fid );
      corridor[i].con.push_back( sid );
      
      G[fid].p = corridor[i].s.first;
      G[fid].line_id.insert(i);
      G[sid].p = corridor[i].s.second;
      G[sid].line_id.insert(i);
    }
    
    for(int i = 0; i < corridor.size(); ++i){
      for(int j = i+1; j < corridor.size(); ++j){
	point intersection;
	
	if( intersection_seg( corridor[i].s, corridor[j].s,intersection ) ){
	  int tid;
	  
	  if( interid.find( Point(intersection) ) == interid.end() ){
	    interid[ Point(intersection) ] = id;
	    tid=id;
	    ++id;
	  }else{
	    tid = interid[ Point(intersection) ];
	  }	  
	  corridor[i].con.push_back( tid );
	  corridor[j].con.push_back( tid );
	  
	  G[tid].p = intersection;
	  G[tid].line_id.insert(i);
	  G[tid].line_id.insert(j);
	}
      }
    }
    G.resize(id+1);
    
    elem dx,dy;
    cin >> dx >> dy;

    point demon(dx,dy);
    G[id].p=demon;
    
    for(int i = 0; i < corridor.size(); ++i){
      if( ccw( corridor[i].s.first, corridor[i].s.second, demon ) == OVER ){
	G[id].line_id.insert(i);
	corridor[i].con.push_back( id );
      }
    }

    ans = dijkstra( corridor, G, id );
    
    printf("%.8lf\n",ans);
  }
  return 0;
}