/* dij+两点间距离 */ #include<stdio.h> #include<string.h> #include<stdlib.h> #include<algorithm> #include<iostream> #include<math.h> using namespace std; const int maxn = 205;//point number const int maxm = 105;//line number const double inf = 99999999; const double eps = 1e-8; struct POINT{ double x,y; int f; }S,T; struct LINE{ double x1,y1,x2,y2; int f; }; int cnt_line,cnt_point; POINT point[ maxn ]; LINE line[ maxm ]; double mat[ maxn ][ maxn ]; double dist( POINT a,POINT b ){ double sum = (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y); return sqrt( sum ); } double xmult( POINT a,POINT b,POINT c ){ return ( a.x-c.x )*( b.y-c.y )-( a.y-c.y )*( b.x-c.x ); } bool inLine( LINE now,POINT p ){ double minx,maxx,miny,maxy; minx=min( now.x1,now.x2 ); maxx=max( now.x1,now.x2 ); miny=min( now.y1,now.y2 ); maxy=max( now.y1,now.y2 ); if( p.x>=minx&&p.x<=maxx&&p.y>=miny&&p.y<=maxy ) return true; else return false; } bool Intersection( LINE one,LINE two ){ double d1,d2,d3,d4; POINT t1,t2,t3,t4; t1.x = one.x1,t1.y = one.y1,t2.x = one.x2,t2.y = one.y2; t3.x = two.x1,t3.y = two.y1,t4.x = two.x2,t4.y = two.y2; d1=xmult( t3,t2,t1 ); d2=xmult( t4,t2,t1 ); d3=xmult( t1,t3,t4 ); d4=xmult( t2,t3,t4 ); if( d1*d2<0&&d3*d4<0 ) return true;//相互跨过 if( d1==0&&inLine( one,t3 )==true ) return true; if( d2==0&&inLine( one,t4 )==true ) return true; if( d3==0&&inLine( two,t1 )==true ) return true; if( d4==0&&inLine( two,t2 )==true ) return true;//分别表示某个点在一条直线上的情况 return false; } void init(){ cnt_line = cnt_point = 0; for( int i=0;i<maxn;i++ ){ for( int j=0;j<maxn;j++ ){ mat[ i ][ j ] = inf; } } }//init void addline( double x1,double y1,double x2,double y2 ){ line[ cnt_line ].x1=x1,line[ cnt_line ].y1=y1; line[ cnt_line ].x2=x2,line[ cnt_line ].y2=y2; cnt_line++; } void addpoint( double x,double y ){ point[ cnt_point ].x = x; point[ cnt_point ].y = y; cnt_point++; } bool test( POINT a,POINT b ){ LINE tt; tt.x1 = a.x,tt.y1 = a.y; tt.x2 = b.x,tt.y2 = b.y; //printf("a.flag:%d b.flag:%d\n",a.f,b.f); for( int i=0;i<cnt_line;i++ ){ if( a.f!=line[ i ].f && b.f!=line[ i ].f && Intersection( tt,line[ i ] )==1 ) return false; } return true; } double dij( int s,int t ){ int vis[ maxn ]; double dis[ maxn ]; for( int i=0;i<cnt_point;i++ ){ dis[ i ] = mat[ s ][ i ]; vis[ i ] = 0; } dis[ s ] = 0; vis[ s ] = 1; //double sum = 0; for( int i=0;i<cnt_point;i++ ){ int k; double tmax; k =-1,tmax = inf; for( int j=0;j<cnt_point;j++ ){ if( vis[ j ]==0&&tmax>dis[ j ] ){ tmax = dis[ j ]; k=j; } } if( k==-1 ) break; vis[ k ] = 1; //sum += tmax; for( int j=0;j<cnt_point;j++ ){ if( vis[ j ]==0&&dis[ j ]>dis[ k ]+mat[ k ][ j ] ){ dis[ j ] = dis[ k ]+mat[ k ][ j ]; } } } return dis[ t ]; } int main(){ int m; while( scanf("%d",&m),m!=-1 ){ init(); S.x = 0.0,S.y = 5.0; T.x = 10.0,T.y = 5.0; if( m==0 ){ printf("%.2lf\n",dist( S,T )); continue; } int flag = 0; point[ cnt_point ].f = flag++; addpoint( S.x,S.y ); point[ cnt_point ].f = flag++; addpoint( T.x,T.y );//start and end double x,y1,y2,y3,y4; for( int num=1;num<=m;num++ ){ scanf("%lf%lf%lf%lf%lf",&x,&y1,&y2,&y3,&y4); line[ cnt_line ].f = flag; addline( x,0.0,x,y1 ); line[ cnt_line ].f = flag; addline( x,y2,x,y3 ); line[ cnt_line ].f = flag; addline( x,y4,x,10.0 );//这三条线段归为一类 point[ cnt_point ].f = flag; addpoint( x,y1 ); point[ cnt_point ].f = flag; addpoint( x,y2 ); point[ cnt_point ].f = flag; addpoint( x,y3 ); point[ cnt_point ].f = flag; addpoint( x,y4 );//这四个点归为一类 flag++; } //printf("flag:%d\ncnt_point:%d\ncnt_line:%d\n",flag,cnt_point,cnt_line); for( int i=0;i<cnt_point;i++ ){ for( int j=i+1;j<cnt_point;j++ ){ if( point[ i ].f!=point[ j ].f&&test( point[ i ],point[ j ] )==true ){ mat[ i ][ j ] = mat[ j ][ i ] = dist( point[ i ],point[ j ] ); //printf("mat[ %d ][ %d ] = %.2lf\n",i,j,mat[i][j]); } } } if( mat[ 0 ][ 1 ]!=inf ){ printf("%.2lf\n",mat[ 0 ][ 1 ]); continue; } double ans = dij( 0,1 ); printf("%.2lf\n",ans); } return 0; }