#include <iostream>#include <cstring>#include <cstdio>#include <queue>#include <vector>#include <cmath>#define MAXN 3000#define MAXM 2000000#define oo 1000000000#define EP (1e-8)using namespace std;struct point_p { double x,y; point_p () {} point_p (double a,double b) {x=a;y=b;} point_p operator +(point_p b) { return point_p (x + b.x, y + b.y);} point_p operator -(point_p b) { return point_p (x - b.x, y - b.y);} double operator ^(point_p b) { return x * b.y - b.x * y;} double operator *(point_p b) { return x * b.x + y * b.y;} bool operator !=(point_p b){ return !(fabs(x-b.x)<EP&& fabs(y-b.y)<EP); } bool operator ==(point_p b){ return (fabs(x-b.x)<EP&& fabs(y-b.y)<EP); }}p[MAXN];struct Edge { int to; double c; Edge *next;} edges[MAXM],*vhead[MAXN];struct DIS { int to; double d; DIS () {to=d=0;} DIS (int a,double b) {to=a;d=b;}};int n;int V,top;bool vis[MAXM];double dis[MAXN];priority_queue<DIS> d;bool operator <(DIS a,DIS b) {return a.d>b.d;}void add_edge (int x,int y,double d,int &top) { Edge *p = &edges[++top]; p->to = y; p->c = d; p->next = vhead[x]; vhead[x] = p;}double dist (int i,int j) { return sqrt ((p[i].x-p[j].x)*(p[i].x-p[j].x) + (p[i].y-p[j].y)*(p[i].y-p[j].y));}void trace () { int i,j,l=V-2; point_p t1,t2,t(0,-1); add_edge (V-2,V,0,top); add_edge (V-1,V,0,top); for (i=0;i<l;i++) { j = i+1; if (!(j%2)) j++; for (;j<V;j+=2) { t1 = p[j]-p[i]; t2 = p[j+1]-p[i]; if ( !((t1^t)>-EP&&(t^t2)>-EP) ) break; } if (j>=V) add_edge (i,V,p[i].y-p[j-1].y,top); }}void create_map () { int i,j,k; point_p t1,t2,l,r; top = 0; memset (vhead,NULL,sizeof (vhead)); trace (); for (i=0;i<V-2;i++) { j = i+1; if ((fabs(p[i].y-p[j].y)<EP)) j++; l = point_p (-1,0); r = point_p (1,0); for (;j<V;j+=2) { k = j+1; t1 = p[j]-p[i]; t2 = p[k]-p[i]; if ((l^t1) > -EP && (t1^r) > -EP) add_edge (i,j,dist(i,j),top); if ((l^t2) > -EP && (t2^r) > -EP) add_edge (i,k,dist(i,k),top); if ((l^t1) > -EP ) l = t1; if ((t2^r) > -EP ) r = t2; if ((r^l)>-EP) break; } }}double dijkstra (int s,int t,double *dis,priority_queue<DIS> &d) { int i; Edge *p; DIS temp; while (d.size ()) d.pop (); for (i=0;i<=t;i++) if (i!=s) d.push(DIS(i,oo)); else d.push(DIS(s,0)); for (i=0;i<MAXN;i++) vis[i]=0,dis[i]=oo; dis[s]=0; for (;d.size ();) { temp = d.top (); d.pop (); vis[temp.to] = 1; if (vis[t]) break; p = vhead[temp.to]; for (;p!=NULL;p=p->next) if (dis[temp.to]+p->c < dis[p->to]) { dis[p->to]=dis[temp.to]+p->c; d.push(DIS(p->to,dis[p->to])); } } return dis[t];}int main() { int i; double x1,x2,y,ans; while (scanf ("%d",&n),n) { V = 0; scanf ("%lf%lf",&p[V].x,&p[V].y);V++; for (i=0;i<n;i++) { scanf ("%lf%lf%lf",&y,&x1,&x2); p[V].x = x1; p[V++].y = y; p[V].x = x2; p[V++].y = y; } for (i=0;i<=V;i++) vhead[i] = NULL; create_map (); ans = dijkstra (0,V,dis,d); printf ("%.8lfn",ans); } return 0;}
