> 计算几何 + 图论，线段相交判定 + 最短路径算法。
> 考虑如何建图？将图中线段的每一个端点，起始点和终点作为图中的边，考察对于任意节点i和节点j，如果i和j之间没有墙，则建立一条长度为几何距离的边，否则不建立边。
> 如何判断i和j之间是否有墙？创建一条起点为i终点为j的线段，遍历全部的墙（线段），利用计算几何的方法，判断线段是否相交即可。建图完成后，
> 运行从开始点到终点的Dijkstra算法即可，源代码见下：
> 
> #include<cstdio>
> #include<cstring>
> #include<algorithm>
> #include<cmath>
> #include<vector>
> #include<queue>
> using namespace std;
> const double inf = 1e20;
> const double eps = 1e-8;
> const double pi = acos(-1);
> int cmp (double a, double b) {
>     if(fabs(a - b) < 0) {
>         return 0;
>     }
>     if(a > b) {
>         return 1;
>     } else {
>         return -1;
>     }
> }
> double add(double a, double b) {
>     if(abs(a + b) < eps * (abs(a) + abs(b))) {
>         return 0;
>     }
>     return a + b;
> }
> struct P {
>     double x, y;
>     P() {}
>     P(double x, double y): x(x), y(y) {}
>     P operator + (P p) {
>         return P(add(x, p.x), add(y, p.y));
>     }
>     P operator - (P p) {
>         return P(add(x, -p.x), add(y, -p.y));
>     }
>     P operator * (double d) {
>         return P(x * d, y * d);
>     }
>     double operator * (P p) {
>         return add(x * p.x, y * p.y);
>     }
>     double operator ^ (P p) {
>         return add(x * p.y, -y * p.x);
>     }
>     double dist(P p) {
>         return sqrt( (x - p.x) * (x - p.x) + (y - p.y) * (y - p.y) );
>     }
> };
> struct L {
>     P s, e;
>     L() {}
>     L(double a, double b, double c, double d) : s(a, b), e(c, d) {}
>     L(P s, P e): s(s.x, s.y), e(e.x, e.y) {}
>     bool on(P p) {
>         return ((p - s) ^ (p - e)) == 0 && ((p - s) * (p - e)) <= 0;
>     }
>     P intersection(L l) {
>         return s + (e - s) * (((l.s - l.e) ^ (s - l.s)) / ((l.s - l.e) ^ (s - e)));
>     }
>     bool cross(L l) {
>         P p = intersection(l);
>         return on(p) && l.on(p);
>     }
> };
> char buf[1024];
> vector<P> arr_P;
> vector<L> arr_L;
> struct edge {
>     int to;
>     double d;
> };
> 
> typedef pair<double, int> Node;
> vector<edge> G[2048];
> double dist[2048];
> 
> int N;
> int V;
> 
> double dijkstra() {
>     fill(dist, dist + V, inf);
>     priority_queue<Node, vector<Node>, greater<Node> > que;
>     dist[0] = 0;
>     que.push(Node(0, 0));
>     while(!que.empty()) {
>         Node p = que.top();
>         que.pop();
>         int v = p.second;
>         if(dist[v] < p.first) {
>             continue;
>         }
>         for(int i = 0; i < G[v].size(); i ++) {
>             edge & e = G[v][i];
>             if(dist[e.to] > dist[v] + e.d) {
>                 dist[e.to] = dist[v] + e.d;
>                 que.push(Node(dist[e.to], e.to));
>             }
>         }
>     }
>     return dist[V - 1];
> }
> 
> int main() {
>     while(true) {
>         scanf("%d", &N);
>         getchar();
>         if(N == -1) {
>             break;
>         }
>         arr_P.clear();
>         arr_L.clear();
>         for(int i = 0; i < 2048; i ++) {
>             G[i].clear();
>         }
>         arr_P.push_back(P(0, 5));
>         for(int i = 0; i < N; i ++) {
>             gets(buf);
>             int index = 0;
>             int len = strlen(buf);
>             double loc;
>             sscanf(buf,"%lf", &loc);
>             while(index < len && buf[index] != ' ') {
>                 index ++;
>             }
>             index ++;
>             double a, b;
>             sscanf( buf + index,"%lf", &a);
>             arr_P.push_back(P(loc, a));
>             arr_L.push_back(L(loc, 0, loc, a));
>             while(index < len) {
>                 while(index < len && buf[index] != ' ') {
>                     index ++;
>                 }
>                 index ++;
>                 if(index < len) {
>                     sscanf( buf + index, "%lf", &a);
>                 }
>                 while(index < len && buf[index] != ' ') {
>                     index ++;
>                 }
>                 index ++;
>                 if(index >= len) {
>                     arr_P.push_back(P(loc, a));
>                     arr_L.push_back(L(loc, a, loc, 10));
>                 } else {
>                     sscanf(buf + index, "%lf", &b);
>                     arr_P.push_back(P(loc, a));
>                     arr_P.push_back(P(loc, b));
>                     arr_L.push_back(L(loc, a, loc, b));
>                 }
>             }
>         }
>         arr_P.push_back(P(10, 5));
>         V = arr_P.size();
>         for(int i = 0; i < V; i ++) {
>             for(int j = i + 1; j < V; j ++) {
>                 if(arr_P[j].x == arr_P[i].x) {
>                     continue;
>                 }
>                 L line(arr_P[i], arr_P[j]);
>                 bool able = true;
>                 for(int k = 0; k < arr_L.size(); k ++) {
>                     if(arr_L[k].s.x > arr_P[i].x && arr_L[k].s.x < arr_P[j].x) {
>                         if(line.cross(arr_L[k])) {
>                             able = false;
>                             break;
>                         }
>                     }
>                 }
>                 if(able) {
>                     edge e;
>                     e.to = j;
>                     e.d = arr_P[i].dist(arr_P[j]);
>                     G[i].push_back(e);
>                 }
>             }
>         }
>         printf("%.2f\n", dijkstra());
>     }
> }