这题就是，处理出没两个点。假设能够到达，就连一条边，推断可不能够到达，利用线段相交去推断就可以。最后求个最短路就可以
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;struct Point {double x, y;Point() {}Point(double x, double y) {this->x = x;this->y = y;}void read() {scanf("%lf%lf", &x, &y);}
};typedef Point Vector;Vector operator - (Vector A, Vector B) {return Vector(A.x - B.x, A.y - B.y);
}const double eps = 1e-8;int dcmp(double x) {if (fabs(x) < eps) return 0;else return x < 0 ? -1 : 1;
}double Cross(Vector A, Vector B) {return A.x * B.y - A.y * B.x;} //叉积//能够不规范相交
bool SegmentProperIntersection2(Point a1, Point a2, Point b1, Point b2) {double c1 = Cross(a2 - a1, b1 - a1), c2 = Cross(a2 - a1, b2 - a1),c3 = Cross(b2 - b1, a1 - b1), c4 = Cross(b2 - b1, a2 - b1);return max(a1.x, a2.x) >= min(b1.x, b2.x) &&max(b1.x, b2.x) >= min(a1.x, a2.x) &&max(a1.y, a2.y) >= min(b1.y, b2.y) &&max(b1.y, b2.y) >= min(a1.y, a2.y) &&dcmp(c1) * dcmp(c2) <= 0 && dcmp(c3) * dcmp(c4) <= 0;
}const int N = 25;int n;struct Ban {Point p[4];void read() {double a, y[4];scanf("%lf", &a);for (int i = 0; i < 4; i++) {scanf("%lf", &y[i]);p[i] = Point(a, y[i]);}}
} b[N];struct Edge {int u, v;double w;Edge(){}Edge(int u, int v, double w) {this->u = u;this->v = v;this->w = w;}
};vector<Edge> g[N * 4];double dist(Point a, Point b) {double dx = a.x - b.x;double dy = a.y - b.y;return sqrt(dx * dx + dy * dy);
}void add_edge(int u, int v, double d) {g[u].push_back(Edge(u, v, d));g[v].push_back(Edge(v, u, d));
}bool judge(int l, int r, Point aa, Point bb) {for (int i = l; i <= r; i++) {if (!SegmentProperIntersection2(aa, bb, b[i].p[0], b[i].p[1]) && !SegmentProperIntersection2(aa, bb, b[i].p[2], b[i].p[3]))return false;}return true;
}double d[N * 4];
int vis[N * 4];double spfa(int s, int t) {memset(vis, 0, sizeof(vis));queue<int> Q;for (int i = 0; i <= t; i++) d[i] = 1e20;d[0] = 0;vis[0] = 1;Q.push(0);while (!Q.empty()) {int u = Q.front();Q.pop();vis[u] = 0;for (int i = 0; i < g[u].size(); i++) {int v = g[u][i].v;double w = g[u][i].w;if (d[u] + w < d[v]) {d[v] = d[u] + w;if (!vis[v]) {vis[v] = 1;Q.push(v);}}}}return d[t];
}int main() {while (~scanf("%d", &n) && n != -1) {for (int i = 0; i <= n * 4 + 1; i++) g[i].clear();for (int i = 0; i < n; i++)b[i].read();if (judge(0, n - 1, Point(0, 5), Point(10, 5)))add_edge(0, n * 4 + 1, 10);for (int i = 0; i < n; i++) {for (int j = 0; j < 4; j++) {if (judge(0, i - 1, Point(0, 5), b[i].p[j]))add_edge(0, i * 4 + j + 1, dist(Point(0, 5), b[i].p[j]));if (judge(i + 1, n - 1, b[i].p[j], Point(10, 5)))add_edge(n * 4 + 1, i * 4 + j + 1, dist(Point(10, 5), b[i].p[j]));for (int k = i + 1; k < n; k++) {for (int x = 0; x < 4; x++) {if (judge(i + 1, k - 1, b[i].p[j], b[k].p[x]))add_edge(i * 4 + j + 1, k * 4 + x + 1, dist(b[i].p[j], b[k].p[x]));}}}}printf("%.2f\n", spfa(0, n * 4 + 1));}return 0;
}
