POJ 1556 The Doors(計算幾何+最短路)

POJ 1556 The Doors(計算幾何+最短路)

這題就是，處理出沒兩個點，如果可以到達，就連一條邊，判斷可不可以到達，利用線段相交去判斷即可，最後求個最短路即可

代碼：

#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;
}