【POJ-1556】The Doors【线段相交、Dijkstra最短路】

【POJ-1556】The Doors【线段相交、Dijkstra最短路】

问题链接:https://vjudge.net/problem/POJ-1556

Solution:

我们需要建一个带权DAG图,权重是两点间距离,用双精度浮点数记录,点集是由所有输入的点以及(0, 5), (10, 5)两个点组成的集合,两点连接有边的必要条件是:1.起点必须严格在终点的左边,2.从起点到终点的连线不能被墙遮挡。现在需要考虑如何确认没有遮挡,其实很简单,就是线段相交。根据题目的数据输入,我们确定一个处理顺序。

  1. 新建一个空点集,新建一个空邻接表,一个线段集【用来装墙】。
  2. 将点集中加入初始点(0, 5)。
  3. 循环读取4个新的点:
    1. 对于每个读取的点,判断当前点集中的两个横坐标不同的点与新的点连线是否与线段集中横坐标位于两个点之间的线段有相交:
      1. 如果有则遍历另外的两个点。
      2. 如果没有则在邻接表中插入这一条新的边,并且权重是两点距离。
    2. 将新增加的三段墙加入到线段集中。
  4. 将点集中最后加入的四个点在邻接表上与结束点(10, 5)相连。
  5. 使用dijkstra算法找到从初始点(0, 5)到结束点(10, 5)的最短路。

点集、邻接表、线段集都使用vector来实现。假设总共有V个点,则遍历可以连接的点的复杂度是\(O(V^2)\),对于每种连线方式,用来判断与线段相交的复杂度是\(O(E)\),其中E表示墙的数量,显然\(E = \frac{V – 2}{4} \times 3\),所以这个的复杂度也写作\(O(V)\),插入操作的是\(O(1)\)的,我们并不关注,所以第三步的时间复杂度是\(O(V^3)\),之后Dijkstra算法通过使用set实现,其时间复杂度为\(O(E_2logV)\),其中\(E_2\)表示邻接表中边的数量,最差情况下,有:

\(E_2 = V \times (V – 1) – 4 \times 3 \times (V – 2)  = V^2 – 13V + 24\),

也就是说,\(O(E_2logV)\)大致为\(O(V^2logV)\),所以此解法的总体复杂度是\(O(V^2logV) + O(V^3) = O(V^3)\)。

#include <iostream>
#include <set>
#include <vector>
#include <cmath>
// #define DBG

using namespace std;

const int LIM = 1000;
const double INF = 1000000;
struct Node {
    int idx;
    double w;
};
struct Point {
    double x, y;
    int id;
    Point operator - (const Point p) const {
        Point ret = {x - p.x, y - p.y};
        return ret;
    }
    double operator ^ (const Point p) {
        return x * p.y - y * p.x;
    }
};
struct Seg {
    Point s, e;
};
vector<Node> adj[LIM];
double dist[LIM];
int n, size;
struct cmp {
    bool operator()(const int a, const int b) {
        if (dist[a] != dist[b]) return dist[a] < dist[b];
        return a < b;
    }
};

void dijsktra() {
    // init
    for (int i = 0; i <= size; i++) dist[i] = INF;
    dist[0] = 0;
    set<int, cmp> ds;
    ds.insert(0);
    int crt, nx;
    while (!ds.empty()) {
        crt = *ds.begin();
        ds.erase(crt);
        if (crt == size) return;
#ifdef DBG
        printf("%d: dis=%f\n", crt, dist[crt]);
#endif
        for (int i = 0; i < adj[crt].size(); i++) {
            nx = adj[crt][i].idx;
            if (dist[nx] > dist[crt] + adj[crt][i].w) {
                if (dist[nx] != INF) ds.erase(nx);
                dist[nx] = dist[crt] + adj[crt][i].w;
                ds.insert(nx);
            }
        }
    }
}

double getDist(double x1, double y1, double x2, double y2) {
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

enum {CONTER = -1, COL, CLOCK};
int getOrientation(Point &a, Point &b, Point &c) {
    Point v1 = b - a;
    Point v2 = c - a;
    double tmp = v1 ^ v2;
    if (tmp < 0) return CONTER;
    else if (tmp > 0) return CLOCK;
    else return COL;
}

inline double mini(double a, double b) {return a < b ? a : b;}
inline double maxi(double a, double b) {return a > b ? a : b;}
bool onSegment(Point s, Point e, Point p) {
    return p.x >= mini(s.x, e.x) && p.x <= maxi(s.x, e.x)
        && p.y >= mini(s.y, e.y) && p.y <= maxi(s.y, e.y);
}

bool isIntersect(Point a, Point b, Point c, Point d) {
    int oa = getOrientation(a, c, b);
    int ob = getOrientation(a, d, b);
    int oc = getOrientation(c, a, d);
    int od = getOrientation(c, b, d);
    if (oa != ob && oc != od) return true;
    if (!oa && onSegment(a, b, d)) return true;
    if (!ob && onSegment(a, b, c)) return true;
    if (!oc && onSegment(c, d, b)) return true;
    if (!od && onSegment(c, d, a)) return true;
    return false;
}

#ifdef DBG
void show() {
    for (int i = 0; i < size; i++) {
        printf("%d:\n", i);
        for (int j = 0; j < adj[i].size(); j++)
            printf("\t%d", adj[i][j].idx);
        putchar('\n');
    }
}
#endif

int main(void) {
    double y[4];
    while (~scanf("%d", &n) && n != -1) {
        // To store the barriers
        vector<Seg> barset;
        vector<Seg>::iterator ite;
        // To store the current points
        vector<Point> pset;
        vector<Point>::iterator pite;
        // init the adjacent table
        for (int i = 0; i < LIM; i++) adj[i].clear();
        // put initial point (0, 5) into pset
        Point crt = {0, 5, 0};
        pset.push_back(crt);
        size = 1;
        for (int i = 0; i < n; i++, size = pset.size()) {
            scanf("%lf%lf%lf%lf%lf", &crt.x, y, y + 1, y + 2, y + 3);
            // iterate all possible way to build a path between the point in
            // pset, and the point which is new.
            for (pite = pset.begin(); pite != pset.end(); pite++) {
                for (int i = 0; i < 4; i++) {
                    crt.y = y[i];
                    bool flag = true;
                    for (ite = barset.begin(); ite != barset.end(); ite++) {
                        if ((*ite).s.x <= (*pite).x) continue;
                        if (isIntersect(*pite, crt, (*ite).s, (*ite).e)) {
                            flag = false;
                            break;
                        }
                    }
                    if (flag) {
                        Node tmp = {size + i, getDist((*pite).x, (*pite).y, crt.x, crt.y)};
                        adj[(*pite).id].push_back(tmp);
                    }
                }
            }
            crt.id = size, crt.y = y[0];
            pset.push_back(crt);
            crt.id = size + 1, crt.y = y[1];
            pset.push_back(crt);
            crt.id = size + 2, crt.y = y[2];
            pset.push_back(crt);
            crt.id = size + 3, crt.y = y[3];
            pset.push_back(crt);
            Seg tmp = {{crt.x, 0}, {crt.x, y[0]}};
            barset.push_back(tmp);
            tmp.s.y = y[1], tmp.e.y = y[2];
            barset.push_back(tmp);
            tmp.s.y = y[3], tmp.e.y = 10;
            barset.push_back(tmp);
        }
        crt.x = 10, crt.y = 5, crt.id = size;
        for (pite = pset.begin(); pite != pset.end(); pite++) {
            bool flag = true;
            for (ite = barset.begin(); ite != barset.end(); ite++) {
                if ((*ite).s.x <= (*pite).x) continue;
                if (isIntersect(*pite, crt, (*ite).s, (*ite).e)) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                Node tmp = {crt.id, getDist((*pite).x, (*pite).y, crt.x, crt.y)};
                adj[(*pite).id].push_back(tmp);
            }
        }
#ifdef DBG
        show();
#endif
        dijsktra();
        printf("%.2f\n", dist[size]);
    }
    return 0;
}