#include #include #include #include #include #include #include #include using namespace std; static const double EPS = 0.00000001; /** geometric data structures and algorithms **/ typedef complex Point; typedef pair LineSeg; namespace std{ bool operator<( const Point& lhs, const Point& rhs ) { if( lhs.real() != rhs.real() ) return lhs.real() < rhs.real(); return lhs.imag() < rhs.imag(); } } double inner(Point p, Point q) { return real(conj(p)*q); } double outer(Point p, Point q) { return imag(conj(p)*q); } bool is_on( const LineSeg& ls, const Point& pt ) { Point v1 = pt-ls.first; Point v2 = ls.second-ls.first; Point pt_proj = ls.first + v2 * inner(v1,v2) / norm(v2); return abs(pt_proj - pt) < 0.0000001; // eps } bool cross( const LineSeg& ls1, const LineSeg& ls2, Point* pt ) { Point p1=ls1.first, d1=ls1.second-ls1.first; Point p2=ls2.first, d2=ls2.second-ls2.first; double f = outer(d1,d2); if( abs(f) == 0 ) return false; double s = outer(p2-p1, d2)/f; double t = outer(p1-p2, d1)/-f; if( s<-EPS || 1+EPS Edge; typedef vector Edges; typedef map Graph; namespace std{ bool operator<( const Edge& e1, const Edge& e2 ) { return e1.second > e2.second; // intentionally reversed for use in prioQ } } map dijkstra( Graph& G, const Point& s ) { map answer; priority_queue Q; Q.push(Edge(s,0)); while( !Q.empty() ) { Edge e = Q.top(); Q.pop(); if( answer.count(e.first) ) continue; answer[e.first] = e.second; Edges& ne = G[e.first]; for(int i=0; i!=ne.size(); ++i) if( !answer.count(ne[i].first) ) Q.push( Edge(ne[i].first, e.second+ne[i].second) ); } return answer; } /** main **/ double solve( const vector& ls, const Point& s ) { // First, construct the set of significant points, // which are the vertices of the representing graph vector< set > cross_pts(ls.size()); for(int i=0; i!=ls.size(); ++i) { // edges cross_pts[i].insert( ls[i].first ); cross_pts[i].insert( ls[i].second ); // starting point if( is_on(ls[i], s) ) cross_pts[i].insert(s); // crossing points for(int j=i+1; j!=ls.size(); ++j) { Point pt; if( cross(ls[i], ls[j], &pt) ) { cross_pts[i].insert(pt); cross_pts[j].insert(pt); } } } // Next, construct the graph Graph G; for(int i=0; i!=cross_pts.size(); ++i) { set::iterator it = cross_pts[i].begin(); Point prev = *it; while( ++it != cross_pts[i].end() ) { Point cur = *it; G[prev].push_back( Edge(cur, abs(cur-prev)) ); G[cur].push_back( Edge(prev, abs(cur-prev)) ); prev = cur; } } assert( G.count(s) ); // dijkstra shortest path for all vertices map ds = dijkstra( G, s ); // for all edges, calculate the furthest point double dist = 0; for(Graph::iterator it=G.begin(); it!=G.end(); ++it) { //cerr<first<second.begin(); jt!=it->second.end(); ++jt) { //cerr<<" "<first<first) ); assert( ds.count(jt->first) ); double x = ds[it->first]; double y = ds[jt->first]; double d = jt->second; //cerr << " #" << x << " " << y << " : " << d << endl; if(x>y) swap(x,y); double t = y + (d-(y-x))/2; dist = max(t, dist); } } return dist; } int main() { for(int N; cin>>N,N;) { vector ls; Point s; // input { for(int i=0; i!=N; ++i) { double x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; ls.push_back( LineSeg(Point(x1,y1), Point(x2,y2)) ); } double sx, sy; cin >> sx >> sy; s = Point(sx, sy); } // solve and output cout << setiosflags(ios::fixed) << setprecision(8) << solve(ls, s) << endl; } }