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<iostream>
#include<stdio.h>
#include<complex>
#include<cfloat>
#include<cassert>
#include<cmath>
#include<vector>
#include<queue>
#include<algorithm>

using namespace std;



#define EPS (1e-8)
#define equals(a, b) (abs((a) - (b)) < EPS )

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

    double absolute() { return sqrt(norm());}
    double norm() { return x*x + y*y; }

    bool operator < ( const Point &p ) const{
	return x != p.x ? x < p.x : y < p.y;
    }

    bool operator == ( const Point &p ) const {
	return abs(x-p.x) < EPS && abs(y-p.y) < EPS;
    }
};

typedef Point Vector;

class Segment{
    public:
    Point source, target;
    Segment(Point s = Point(), Point t = Point()): source(s), target(t){}
};

double norm( Vector a ){
    return a.x*a.x + a.y*a.y;
}

double absolute( Vector a ){
    return sqrt(norm(a));
}

double getDistance(Vector a, Vector b){
    return absolute(a - b); 
}

// dot product
double dot(Vector a, Vector b){
    return a.x*b.x + a.y*b.y;
}

// cross product
double cross(Vector a, Vector b){
    return a.x*b.y - a.y*b.x;
}

Point project( Segment s, Point p ){
    Vector base = s.target - s.source;
    double t = dot(p - s.source, base)/norm(base);
    return s.source + (base)*t;
}

Point reflect( Segment s, Point p ){
    return p + (project(s, p) - p)*2.0;
}

// verified by uoa2062
bool isOnSegment( Point a, Point b, Point c){
    if ( a == c || b == c ) return true;
    return (absolute(a-c) + absolute(c-b) < absolute(a-b) + EPS );
}

bool isOrthogonal( Vector a, Vector b ){
     return equals( dot(a, b), 0.0 );
}

bool isOrthogonal( Point a1, Point a2, Point b1, Point b2 ){
    return isOrthogonal( a1 - a2, b1 - b2 );
}

bool isOrthogonal( Segment s1, Segment s2 ){
    return equals( dot(s1.target - s1.source, s2.target - s2.source), 0.0 );
}

bool isParallel( Vector a, Vector b ){
    return equals( cross(a, b), 0.0 );
}

bool isParallel( Point a1, Point a2, Point b1, Point b2){
    return isParallel( a1 - a2, b1 - b2 );
}

bool isParallel( Segment s1, Segment s2 ){
    return equals( cross(s1.target - s1.source, s2.target - s2.source), 0.0 );
}

static const int COUNTER_CLOCKWISE = 1;
static const int CLOCKWISE = -1;
static const int ONLINE_BACK = 2;
static const int ONLINE_FRONT = -2;
static const int ON_SEGMENT = 0;

int ccw( Point p0, Point p1, Point p2 ){
    Vector a = p1 - p0;
    Vector 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;
}

// intersect Segment p1-p2 and Segment p3-p4 ?
bool isIntersect(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 );
}

// intersect Segment s1 and Segment s2 ?
// verified by 920, 833, 866, uoa2062
bool isIntersect(Segment s1, Segment s2){
    return isIntersect(s1.source, s1.target, s2.source, s2.target);
}

// verified by 920, 833, uoa2062
Point getCrossPoint(Segment s1, Segment s2){
    assert( isIntersect(s1, s2) );
    Vector base = s2.target - s2.source;
    double d1 = absolute(cross(base, s1.source - s2.source));
    double d2 = absolute(cross(base, s1.target - s2.source));
    double t = d1/(d1 + d2);
    return s1.source + (s1.target - s1.source)*t;
}


#define MAX 2000
#define NMAX 80000
#define LIMIT FLT_MAX

class Edge{
    public:
    int target;
    double dist;
    Edge(){}
    Edge(int target, double dist): target(target), dist(double(dist)){}
};

class Graph{
    public:
    vector<Edge> adjList[NMAX];
    int start;

    Graph(){
	for ( int i = 0; i < NMAX; i++ ) adjList[i].clear();
    }
    
    void connect( int i, int j, double d ){
	adjList[i].push_back(Edge(j, d));
	adjList[j].push_back(Edge(i, d));
    }
};

class QNode{
    public:
    int index;
    double cost;
    QNode(){}
    QNode( int index, double cost ): index(index), cost(cost){}
    
    bool operator < ( const QNode &q ) const { return cost > q.cost; }
};

class Node{
    public:
    Point p;
    int id;
    Node(){}
    Node( Point p, int id): p(p), id(id){}
    bool operator < ( const Node &n) const {
	return p < n.p;
    }
};

int nnode;
Point SP[NMAX];

int getIndex( Point p ){
    SP[nnode++] = p;
    return nnode-1;
}

void makeGraph(Graph &g, Segment S[MAX], int N, Point s ){
    Segment base, target;
    Node L[NMAX];
    int beg, p = 0;
    bool startSet = false;
    nnode = 0;
    for ( int b = 0; b < N; b++ ){
	base = S[b];
	beg = p;

	if ( !startSet && isOnSegment(base.source, base.target, s) ){
	    L[p++] = Node(s, getIndex(s));
	    startSet = true;
	}

	L[p++] = Node(base.source, getIndex(base.source));
	L[p++] = Node(base.target, getIndex(base.target));

	for ( int t = 0; t < N; t++ ){
	    if ( t == b ) continue;
	    target = S[t];
	    if ( !isIntersect(base, target) ) continue;
	    Point cp = getCrossPoint(base, target);
	    L[p++] = Node(cp, getIndex(cp));
	}

	sort(L + beg, L + p );

	for ( int i = beg; i < p-1; i++ ){
	    g.connect(L[i].id, L[i+1].id, getDistance(L[i].p, L[i+1].p));
	}
    }

    sort( L, L + p );

    for ( int i = 0; i < p-1; i++ ){
      //	if ( eq(L[i].p, L[i+1].p) ) 
      if ( L[i].p ==  L[i+1].p ) 
	    g.connect( L[i].id, L[i+1].id, 0.0);
      //	if ( eq(L[i].p, s) ) g.start = L[i].id;
      if ( L[i].p == s ) g.start = L[i].id;
    }

}

double dijkstra(Graph g){
    bool visited[NMAX];
    double D[NMAX];
    priority_queue<QNode> PQ;
    
    for ( int i = 0; i < nnode; i++ ) {
	visited[i] = false;
	D[i] = LIMIT;
    }

    for ( int i = 0; i < g.adjList[g.start].size(); i++ ){
	Edge v = g.adjList[g.start][i];
	PQ.push(QNode(v.target, v.dist) );
	D[v.target] = v.dist;
    }

    visited[g.start] = true;
    D[g.start] = 0.0;

    QNode u;

    while( !PQ.empty() ){
	u = PQ.top(); PQ.pop();
	if ( visited[u.index] ) continue;
	visited[u.index] = true;
	for ( int i = 0; i < g.adjList[u.index].size(); i++ ){
	    Edge v = g.adjList[u.index][i];
	    if ( visited[v.target] ) continue;
	    if ( D[u.index] + v.dist < D[v.target] ){
		D[v.target] = D[u.index] + v.dist;
		PQ.push(QNode(v.target, D[v.target]));
	    }
	}
    }

    double mdist = 0.0;

    for ( int i = 0; i < nnode; i++ ){
	mdist = max(mdist, D[i] );
	for ( int k = 0; k < g.adjList[i].size(); k++ ){
	    int j = g.adjList[i][k].target;
	    double d = getDistance(SP[i], SP[j]);
	    mdist = max(mdist, (double)(min(D[i], D[j]) + (d - abs(D[i]-D[j]))/2.0));
	}
    }
    return mdist;
}

int main(){
    int N;
    Segment S[MAX];

    while( cin >> N && N ){
	Point p1, p2;
	for ( int i = 0; i < N; i++ ){
	    cin >> p1.x; cin >> p1.y;
	    cin >> p2.x; cin >> p2.y;
	    S[i] = Segment(p1, p2);
	}
	cin >> p1.x; cin >> p1.y;
	Graph g;
	makeGraph(g, S, N, p1);
	printf("%.5lf\n", dijkstra(g));
    }

    return 0;
}

/**
daaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaadaaaaaaaaaaaaaadaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaadaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaadaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaadaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaadaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaadaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaadaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaadaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaadaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaadaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaadaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaadaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaadaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaadaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaa


*/