這題就是,處理出沒兩個點,如果可以到達,就連一條邊,判斷可不可以到達,利用線段相交去判斷即可,最後求個最短路即可
代碼:
#include#include #include #include #include using namespace std; #include #include #include #include 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 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 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; }