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

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:(!equals(y,p.y)&&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);
}


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

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

Point sp;

vector<vector<Edge> > segmentArrangement(vector<Segment> &vs,vector<Point> &ps) {
  ps.push_back(sp);

  rep(i,vs.size()) ps.push_back( (vs[i].p1+vs[i].p2) / 2.0 );

  rep(i,vs.size()) ps.push_back(vs[i].p1), ps.push_back(vs[i].p2);
  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])));

  sort(ps.begin(),ps.end());  
  ps.erase(unique(ps.begin(),ps.end()),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(list.begin(),list.end());
    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;
}

int E;
vector<Segment> segs;

bool  LT(double a,double b) { return !equals(a,b) && a < b; }
bool LTE(double a,double b) { return  equals(a,b) || a < b; }

// --作成中-- 

Point vir;
bool comp_dist(const Point &a,const Point &b){ return LT(abs(vir-a),abs(vir-b)); }

const int MAX_N = 2000;
int uf[MAX_N];
void init(int N=MAX_N) { rep(i,N) uf[i] = i; }
int find(int x) { 
  if( x == uf[x] ) return x;
  return uf[x] = find(uf[x]);
}
void unit(int x,int y){
  x = find(x), y = find(y);
  if( x != y ) uf[x] = y;  
}

void segmentMerge(vector<Segment> &vec,vector<Segment> &ret){
  init(vec.size());
  rep(i,vec.size()) {
    rep(j,vec.size()) {
      if( equals(cross(vec[i].p1-vec[i].p2,vec[j].p1-vec[j].p2),0.0) && intersectSS(vec[i],vec[j]) ) unit(i,j);
    }
  }

  ret.clear();
  vector<int> color;
  rep(i,vec.size()) color.push_back(find(i));
  sort(color.begin(),color.end());
  color.erase(unique(color.begin(),color.end()),color.end());
  rep(i,color.size()) {
    vector<Point> vp;
    rep(j,vec.size()) if( color[i] == find(j) ) vp.push_back(vec[j].p1), vp.push_back(vec[j].p2);
    sort(vp.begin(),vp.end());
    vp.erase(unique(vp.begin(),vp.end()),vp.end());
    assert( vp.size() >= 2 ); // 線分じゃなくて点
    vir = vp[0];
    sort(vp.begin(),vp.end(),comp_dist);
    ret.push_back(Segment(vp.front(),vp.back()));
  }
}

// --作成中--

const double DINF = 1e20;

struct Data {
  int cur;
  double weight;
  bool operator < ( const Data &data ) const { return !equals(weight,data.weight) && weight > data.weight; }
};

void dijkstra(vector<vector<Edge> > &G,vector<Point> &ps){
  int sindex = -1;
  rep(i,(int)ps.size()) if( ps[i] == sp ) { sindex = i; break; }
  assert( sindex != -1 );

  int V = ps.size();
  priority_queue<Data> Q;
  Q.push((Data){sindex,0});
  vector<double> mindist(V,DINF);
  mindist[sindex] = 0;
  while( !Q.empty() ){
    Data data = Q.top(); Q.pop();
    
    if( LT(mindist[data.cur],data.weight) ) continue;

    rep(i,G[data.cur].size()){
      int to = G[data.cur][i].to;
      if( LT(data.weight+G[data.cur][i].cost,mindist[to]) ){
        mindist[to] = data.weight+G[data.cur][i].cost;
        Q.push((Data){to,mindist[to]});
      }
    }

  }

  double maxi = 0;
  rep(i,V) {
    assert( !equals(DINF,mindist[i]) );
    maxi = max(maxi,mindist[i]);
  }

  printf("%.10lf\n",maxi);

}

void compute(){
  vector<Segment> buf = segs;
  //segmentMerge(segs,buf);  

  vector<Point> ps;
  vector<vector<Edge> > G = segmentArrangement(buf,ps);

  dijkstra(G,ps);

}

int main(){
  while( cin >> E, E ){
    segs.resize(E);
    rep(i,E) cin >> segs[i].p1.x >> segs[i].p1.y >> segs[i].p2.x >> segs[i].p2.y;
    cin >> sp.x >> sp.y;
    compute();
  }
  return 0;
}