这题就是，，处理出没两个点，如果可以到达，就连一条边，判断可不可以到达，利用线段相交去判断即可，最后求个最短路即可
代码：
#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;}
在前进的路上，主动搬开别人脚下的绊脚石，有时往往也是为自己铺路。
