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 MAX 100000
#define inf 1<<29
#define linf 1e18
#define eps (1e-8)
#define mod 1000000007
#define pi M_PI
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define pd(a) printf("%.10f\n",(double)(a))
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(a)-1;(b)<=i;i--)
#define equals(a,b) (fabs((a)-(b))<eps)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<double,int> pdi;
typedef pair<int,double> pid;
typedef vector<int> vi;
typedef vector<pii> vpi;
const int dx[8]={1,0,-1,0,1,1,-1,-1};
const int dy[8]={0,1,0,-1,1,-1,1,-1};

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 k){ return Point(x*k,y*k);}
  Point operator/(double k){ return Point(x/k,y/k);}
  bool operator<(Point p)const{ return (x!=p.x ? x<p.x : y<p.y);}
  bool operator==(Point p)const{ return fabs(x-p.x)<eps && fabs(y-p.y)<eps;}
 
  double abs(){ return sqrt(norm());}
  double norm(){ return (x*x+y*y);}
};
typedef Point Vector;
typedef vector<Point> Polygon;
 
class Segment{
public:
  Point p1,p2;
  Segment(Point p1=Point(),Point p2=Point()):p1(p1),p2(p2){}
};
typedef Segment Line;
 
double norm(Vector a){ return (a.x*a.x+a.y*a.y);}
double abs(Vector a){ return sqrt(norm(a));}
double dot(Vector a,Vector b){ return (a.x*b.x+a.y*b.y);}
double cross(Vector a,Vector b){ return (a.x*b.y-a.y*b.x);}
 
bool isParallel(Segment s,Segment t){
  return equals(cross(s.p1-s.p2,t.p1-t.p2),0.0);
}
 
int ccw(Point p0,Point p1,Point p2){
  Vector a=p1-p0;
  Vector b=p2-p0;
  if(cross(a,b)>eps)return 1;
  if(cross(a,b)<-eps)return -1;
  if(dot(a,b)<-eps)return 2;
  if(a.norm()<b.norm())return -2;
  return 0;
}
 
bool intersect(Point p1,Point p2,Point p3,Point p4){
  return (ccw(p1,p2,p3)*ccw(p1,p2,p4)<=0 &&
          ccw(p3,p4,p1)*ccw(p3,p4,p2)<=0);
}
 
bool intersect(Segment s1,Segment s2){
  return intersect(s1.p1,s1.p2,s2.p1,s2.p2);
}
 
Point getCrossPointLL(Line a,Line b){
  double A=cross(a.p2-a.p1,b.p2-b.p1);
  double B=cross(a.p2-a.p1,a.p2-b.p1);
  if(abs(A)<eps || abs(B)<eps)return b.p1;
  return b.p1+(b.p2-b.p1)*(B/A);
}
 
bool merge_if_able(Segment &s,Segment t) {
  if(!isParallel(s,t))return false;
  if(ccw(s.p1,t.p1,s.p2)==1 ||
     ccw(s.p1,t.p1,s.p2)==-1)return false;
  if(ccw(s.p1,s.p2,t.p1)==-2 ||
     ccw(t.p1,t.p2,s.p1)==-2)return false;
  s=Segment(min(s.p1,t.p1),max(s.p2,t.p2));
  return true;
}
 
void merge(vector<Segment>& v) {
  for(int i=0;i<v.size();i++){
    if(v[i].p2<v[i].p1)swap(v[i].p2,v[i].p1);
  }
  for(int i=0;i<v.size();i++)
    for(int j=i+1;j<v.size();j++)
      if(merge_if_able(v[i],v[j]))
        v[j--]=v.back(),v.pop_back();
}
 
typedef vector<vector<int> > Graph;
 
Graph SegmentArrangement(vector<Segment> v,vector<Point> &ps){
  for(int i=0;i<v.size();i++){
    ps.push_back(v[i].p1);
    ps.push_back(v[i].p2);
    for(int j=i+1;j<v.size();j++){
      if(intersect(v[i],v[j]))ps.push_back(getCrossPointLL(v[i],v[j]));
    }
  }
  //sort(ps.begin(),ps.end());
  //ps.erase(unique(ps.begin(),ps.end()),ps.end());
  Graph g(ps.size());
  for(int i=0;i<v.size();i++){
    vector<pair<double,int> > list;
    for(int j=0;j<ps.size();j++)
      if(ccw(v[i].p1,v[i].p2,ps[j])==0)
        list.push_back(mp(norm(v[i].p1-ps[j]),j));
    sort(list.begin(),list.end());
    for(int j=0;j<list.size()-1;j++){
      int a=list[j].s,b=list[j+1].s;
      g[a].push_back(b);
      g[b].push_back(a);
    }
  }
  return g;
}

Graph g;
vector<Point> vp;
int n;
vector<Segment> vs;
Point s;
int start;
double d[MAX];

void init(){
  vs.clear();
  vp.clear();
  g.clear();
}

void dijkstra(){
  FOR(i,0,MAX)d[i]=linf;
  priority_queue<pdi,vector<pdi>,greater<pdi> > pq;
  pq.push(mp(0.0,start));
  d[start]=0.0;

  while(pq.size()){
    pdi u=pq.top();
    pq.pop();

    if(d[u.s]-u.f<-eps)continue;

    FOR(i,0,g[u.s].size()){
      int next=g[u.s][i];
      double cost=abs(vp[u.s]-vp[next]);
      if(u.f+cost-d[next]<-eps){
        d[next]=u.f+cost;
        pq.push(mp(d[next],next));
      }
    }
  }
}

double solve(){
  double res=0;
  merge(vs);
  vp.pb(s);
  g=SegmentArrangement(vs,vp);
  FOR(i,0,vp.size())if(s==vp[i])start=i;
  dijkstra();
  FOR(i,0,vp.size()){
    if(d[i]!=linf){
      res=max(res,d[i]);
      FOR(j,0,g[i].size()){
        int next=g[i][j];
        double cost=abs(vp[next]-vp[i]);
        res=max(res,min(d[i],d[next])+(cost-abs(d[i]-d[next]))/2.0);
      }
    }
  }
  return res;
}

int main()
{
  while(cin>>n && n){
    init();
    FOR(i,0,n){
      double a,b,c,d;
      cin>>a>>b>>c>>d;
      vs.pb(Segment(Point(a,b),Point(c,d)));
    }
    cin>>s.x>>s.y;
    pd(solve());
  }
  return 0;
}