1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <cmath>  5 #include <algorithm>  6 using namespace std;  7   8 const int Max=100;  9 const int M=3000; 10 const int inf=10000; 11 typedef struct pt{ 12     double x,y; 13     int belong; 14 }Point; 15  16 typedef struct pl{ 17     Point start,end; 18 }Pleg; 19 int how_point,how_pleg; 20 Point pot[Max]; 21 Pleg edge[Max]; 22  23 double multi(Point p1, Point p2,Point p0){ 24     return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y); 25 } 26 int head[Max],tot; 27 struct { 28     int u,v; 29     double w; 30     int next; 31 }de[M]; 32 double dis[Max]; 33 bool vis[Max]; 34  35 bool tested(Pleg v1,Point s,Point t){ 36     Pleg v2; v2.start=s; v2.end=t; 37     if(max(v1.start.x,v1.end.x)>=min(v2.start.x,v2.end.x)&& 38        max(v2.start.x,v2.end.x)>=min(v1.start.x,v1.end.x)&& 39        max(v1.start.y,v1.end.y)>=min(v2.start.y,v2.end.y)&& 40        multi(v2.start,v1.end,v1.start)*multi(v1.end,v2.end,v1.start)>0&& 41        multi(v1.start,v2.end,v2.start)*multi(v2.end,v1.end,v2.start)>0) 42        return false; 43        return true; 44 } 45  46 void addedge(int u,int v,double w){ 47     de[tot].u=u; 48     de[tot].v=v; 49     de[tot].w=w; 50     de[tot].next=head[u]; 51     head[u]=tot++; 52 } 53  54 void dijk(int s,int t){ 55     vis[s]=true; dis[s]=0; 56     for(int i=head[s];i!=-1;i=de[i].next){ 57         int v=de[i].v; 58         if(dis[v]>de[i].w) 59         dis[v]=de[i].w; 60     } 61     for(int i=0;i<=how_point;i++){ 62         int p=s; double min=inf; 63         for(int j=0;j<=how_point;j++){ 64             if(dis[j]<min&&!vis[j]){ 65                 min=dis[j]; p=j; 66             } 67         } 68         if(p==s) return ; 69         vis[p]=true; 70         for(int k=head[p];k!=-1;k=de[k].next){ 71             int v=de[k].v; 72             if(min+de[k].w<dis[v]&&!vis[v]){ 73                 dis[v]=min+de[k].w; 74             } 75         } 76     } 77 } 78  79 int main(){ 80     pot[0].x=0; pot[0].y=5; 81     int n; double a,b,c,d,e; Point tmp; 82     while(scanf("%d",&n)!=EOF){ 83         if(n==-1) break; 84         how_pleg=0;how_point=0; 85         memset(head,-1,sizeof(head)); tot=0; 86         memset(vis,false,sizeof(vis)); 87         for(int i=0;i<Max;i++) 88         dis[i]=inf; 89         for(int i=1;i<=n;i++){ 90             scanf("%lf%lf%lf%lf%lf",&a,&b,&c,&d,&e); 91             how_pleg++;    how_point++; 92             tmp.x=a; tmp.y=0; tmp.belong=how_pleg; 93             pot[how_point].x=a; pot[how_point].y=b; pot[how_point].belong=how_pleg; 94             edge[how_pleg].start=tmp; edge[how_pleg].end=pot[how_point]; 95             how_point++; how_pleg++; 96             pot[how_point].x=a; pot[how_point].y=c; pot[how_point].belong=how_pleg; 97             how_point++; 98             pot[how_point].x=a; pot[how_point].y=d; pot[how_point].belong=how_pleg; 99             edge[how_pleg].start=pot[how_point-1]; edge[how_pleg].end=pot[how_point];100             how_point++;  how_pleg++;101             pot[how_point].x=a; pot[how_point].y=e; pot[how_point].belong=how_pleg;102             tmp.x=a; tmp.y=10; tmp.belong=how_pleg;103             edge[how_pleg].start=pot[how_point]; edge[how_pleg].end=tmp;104         }105         how_point++;106         pot[how_point].x=10; pot[how_point].y=5;pot[how_point].belong=how_pleg+1;107         for(int i=0;i<=how_point;i++){108             for(int j=i+1;j<=how_point;j++){109                 int e=pot[j].belong;110                 bool flag=true;111                 for(int k=1;k<e;k++){112                     if(!tested(edge[k],pot[i],pot[j])){113                         flag=false;114                         break;115                     }116                 }117                 if(flag){118                     double x=pot[i].x-pot[j].x;119                     double y=pot[j].y-pot[i].y;120                     double d=sqrt(x*x+y*y);121                     addedge(i,j,d);122                 }123             }124         }125         dijk(0,how_point);126         printf("%0.2lf\n",dis[how_point]);127     }128 }