一道很好的DP题。预处理每个点对之间是否能直接到达，然后状态很容易划分。
#include <stdio.h>#include <string.h>#include <math.h>#define _0 1e-10int N, b[20][4][20][4], ll;double f[20][4];typedef struct
...{
double x, y[4];
} Wall;Wall w[20];typedef struct...{ double x, y;} Point;typedef struct...{ double x1, y1, x2, y2;} Line;Line l[100];void pf ()...{ int i, j, ii, jj; for ( i = 1; i <= N; i ++ )
...{ for ( j = 0; j < 4; j ++ ) ...{ printf ( "%d ", b[i][j][3][0] );
} printf ( " " ); }}double crossDet ( double x1, double y1, double x2, double y2 )...{ return x1 * y2 - x2 * y1;}double cross ( Point &a, Point &b, Point &c )...{ return crossDet ( b.x - a.x, b.y - a.y, c.x - a.x, c.y - a.y );}double dCmp ( double x )...{ if ( x <_0 && x> - _0 ) return 0; return x > _0 ? 1 : -1;}double dist ( double x1, double y1, double x2, double y2 )...{ return sqrt ( ( y1 - y2 ) * ( y1 - y2 ) + ( x1 - x2 ) * ( x1 - x2 ) );}int segCross ( Point &a, Point &b, Point &c, Point &d )...{ return ( dCmp ( cross ( a, b, d ) ) * dCmp ( cross ( a, b, c ) ) == -1 ) && ( dCmp ( cross ( c, d, a ) ) * dCmp ( cross ( c, d, b ) ) == -1 );}int reach ( double x1, double y1, double x2, double y2 )...{ //x1 < x2 int i; for ( i = 0; i < ll; i ++ ) ...{ //if ( x1 >= l[i].x1 || x2 <= l[i].x1 ) //continue; Point p1, p2, p3, p4; p1.x = x1, p1.y = y1, p2.x = x2, p2.y = y2; p3.x = l[i].x1, p3.y = l[i].y1, p4.x = l[i].x2, p4.y = l[i].y2; if ( segCross ( p1, p2, p3, p4 ) ) return 0; } return 1;}int init ()...{ scanf ( "%d", &N ); memset ( b, 0, sizeof ( b ) ); if ( N == -1 ) return 0; int i, j, ii, jj; for ( i = 1; i <= N; i ++ ) scanf ( "%lf%lf%lf%lf%lf", &w[i].x, &w[i].y[0], &w[i].y[1], &w[i].y[2], &w[i].y[3] ); for ( i = 1, ll = 0; i <= N; i ++ ) ...{ l[ll].x1 = l[ll].x2 = w[i].x, l[ll].y1 = 0, l[ll ++].y2 = w[i].y[0]; l[ll].x1 = l[ll].x2 = w[i].x, l[ll].y1 = w[i].y[1], l[ll ++].y2 = w[i].y[2]; l[ll].x1 = l[ll].x2 = w[i].x, l[ll].y1 = w[i].y[3], l[ll ++].y2 = 10; } for ( i = 1; i <= N; i ++ ) for ( j = 0; j < 4; j ++ ) ...{ if ( reach ( 0, 5, w[i].x, w[i].y[j] ) ) b[i][j][0][0] = b[0][0][i][j] = 1; if ( reach ( 10, 5, w[i].x, w[i].y[j] ) ) b[i][j][N + 1][0] = b[N + 1][0][i][j] = 1; for ( ii = i + 1; ii <= N; ii ++ ) for ( jj = 0; jj < 4; jj ++ ) if ( reach ( w[i].x, w[i].y[j], w[ii].x, w[ii].y[jj] ) ) b[i][j][ii][jj] = b[ii][jj][i][j] = 1; } return 1;}void dp ()...{ if ( reach ( 0, 5, 10, 5 ) ) ...{ printf ( "%.2f ", 10.00 ); return; } int i, j, ii, jj; double t, tt; for ( i = 1; i <= N; i ++ ) ...{ for ( j = 0; j < 4; j ++ ) ...{ t = 100; if ( b[i][j][0][0] ) ...{ f[i][j] = dist ( 0, 5, w[i].x, w[i].y[j] ); continue; } for ( ii = 1; ii < i; ii ++ ) ...{ for ( jj = 0; jj < 4; jj ++ ) ...{ if ( b[i][j][ii][jj] ) ...{ tt = f[ii][jj] + dist ( w[i].x, w[i].y[j], w[ii].x, w[ii].y[jj] ); if ( t > tt ) t = tt; } } } f[i][j] = t; } } double ans = 100; for ( i = 1; i <= N; i ++ ) ...{ for ( j = 0; j < 4; j ++ ) ...{ if ( b[i][j][N + 1][0] ) ...{ tt = f[i][j] + dist ( w[i].x, w[i].y[j], 10, 5 ); if ( ans > tt ) ans = tt; } } } printf ( "%.2f ", ans );}int main ()...{ //freopen ( "in.txt", "r", stdin ); while ( init () ) ...{ dp (); //pf (); } return 0;}