P3632 [APIO2011] 寻路

寻路

因为只能横平竖直地移动，且不能穿过矩形，所以，我们希望能够建出下图的绿色点

格点

这样的绿色点的特征是：我们确保了可以在绿色点上换飞行方向，从而沿着建出来的边走。这样我们就可以跑最短路算法了。

现在考虑怎么建出这样的点。假定在某个点 $(a,b)$ 并且向左走，那么我们画一条 $y=b$ 的直线，在 $(a,b)$ 左侧且最靠近 $(a,b)$ 的点 $(c,d)$ 就是 Dee 的落脚点，所以在 $(c,d),(a,b)$ 之间连边。

处理完不同矩形之间的边后，我们还需要处理同一个矩形上的点之间的边，因为上面扫描线这一过程可能会产生不在角上的点（图中在边上的绿色点）。我们需要把这些点连接到矩形的角点上。具体而言，我们把扫描线产生的额外点 assign 到矩形的上、下、左、右边上，然后对每个矩形枚举四条边，sort -> unique 之后相邻的点之间连边。

最后，我们在 start 和 end 之间跑一个裸的最短路即可。

Code

实现细节：我们处理两次，一次处理矩形的长 $x=L_i$ ，一次处理矩形的宽 $y=H_i$ . 处理长的时候，我们按 $y$ 坐标从小到大加入待处理队列（我用 map<int,int> 同时维护顺序和线段范围），那么我们可以直接遍历 map，尝试在 it 代表的矩形边和 next(it) 代表的矩形边之间建一条边（如果这两条矩形边在不同的矩形上）。

#include <algorithm>
#include <cassert>
#include <chrono>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <iostream>
#include <map>
#include <queue>
#include <utility>
#include <vector>
using ll        = long long;
using edge      = std::pair<int, ll>;
using vi        = std::vector<int>;
using pil       = std::pair<int, ll>;
using vpil      = std::vector<pil>;
constexpr int N = 1e3 + 5;

struct Rec {
    int l, r, t, b;
    vi onl, onr, ont, onb;
} R[N];
int n, index{0};
std::map<std::pair<int, int>, int> ind;  // (x, y) -> index
std::map<int, std::pair<int, int>> ind2; // index -> (x, y)
std::vector<vpil> G;

int insert(int x, int y) {
    if (ind.find({x, y}) != ind.end()) return ind[{x, y}];
    ind[{x, y}] = ++index;
    ind2[index] = {x, y};
    G.push_back({});
    return index;
}

void run() {
    G.push_back({}); // index 0 is unused
    [&] {
        int a, b, c, d;
        std::cin >> a >> b >> c >> d;
        std::cin >> n;
        for (int i = 1; i <= n; i++) {
            std::cin >> R[i].l >> R[i].b >> R[i].r >> R[i].t;
            if (R[i].l > R[i].r) std::swap(R[i].l, R[i].r);
            if (R[i].b > R[i].t) std::swap(R[i].b, R[i].t);
        }
        R[n + 1] = {a, a, b, b}; // start rectangle
        R[n + 2] = {c, c, d, d}; // end
    }();

    [&] {
        struct segment {
            int id, x, y, end; // end: 0 => bottom, 1 => top
            segment(int i, int x, int y, int e) : id(i), x(x), y(y), end(e) {}
        };
        std::vector<segment> cand;
        for (int i = 1; i <= n + 2; i++) {
            cand.emplace_back(i, R[i].l, R[i].b, 0); // left bottom
            cand.emplace_back(i, R[i].l, R[i].t, 1); // left top
            cand.emplace_back(i, R[i].r, R[i].b, 0); // right bottom
            cand.emplace_back(i, R[i].r, R[i].t, 1);
        }
        std::sort(cand.begin(), cand.end(), [&](const segment &a, const segment &b) {
            if (a.y == b.y) {
                if (a.x == b.x) return a.end < b.end; // bottom before top
                else return a.x < b.x;                // sort by x first
            } else return a.y < b.y;
        });

        std::map<int, int> mp; // x -> id
        for (auto it = cand.begin(); it != cand.end();) {
            int y    = it->y;
            auto tit = it;
            while (tit != cand.end() && tit->y == y) mp.insert({tit->x, tit->id}), tit++;

            // create points
            std::vector<int> indexes;
            for (auto [x, id] : mp) {
                assert(x == R[id].l || x == R[id].r);
                int k = insert(x, y);
                if (x == R[id].l) R[id].onl.push_back(k);
                else R[id].onr.push_back(k);
                indexes.push_back(k);
            }

            // connect edges
            auto p = indexes.begin();
            for (auto pit = mp.begin(); std::next(pit) != mp.end(); pit++, p++) {
                auto nit = std::next(pit);
                auto np  = std::next(p);
                if (nit->second == pit->second) continue; // 同一个蜂巢
                ll len = nit->first - pit->first;
                G[*p].emplace_back(*np, len);
                G[*np].emplace_back(*p, len);
            }

            // update segments
            for (; it != tit; it++)
                if (it->end == 1) mp.erase(it->x);
        }
    }();

    [&] {
        struct segment {
            int id, x, y, end;
        };
        std::vector<segment> cand;
        for (int i = 1; i <= n + 2; i++) {
            cand.emplace_back(i, R[i].l, R[i].t, 0);
            cand.emplace_back(i, R[i].r, R[i].t, 1);
            cand.emplace_back(i, R[i].l, R[i].b, 0);
            cand.emplace_back(i, R[i].r, R[i].b, 1);
        }
        std::sort(cand.begin(), cand.end(), [&](const segment &a, const segment &b) {
            if (a.x == b.x) {
                if (a.y == b.y) return a.end < b.end;
                else return a.y < b.y;
            } else return a.x < b.x;
        });
        std::map<int, int> mp; // y -> id
        for (auto it = cand.begin(); it != cand.end();) {
            int x    = it->x;
            auto tit = it;
            while (tit != cand.end() && tit->x == x) mp.insert({tit->y, tit->id}), tit++;

            // create points
            vi indexes;
            for (auto [y, id] : mp) {
                assert(y == R[id].t || y == R[id].b);
                int k = insert(x, y);
                indexes.push_back(k);
                if (y == R[id].t) R[id].ont.push_back(k);
                else R[id].onb.push_back(k);
            }

            // update edges
            auto p = indexes.begin();
            for (auto pit = mp.begin(); std::next(pit) != mp.end(); pit++, p++) {
                auto nit = std::next(pit);
                auto np  = std::next(p);
                if (nit->second == pit->second) continue;
                ll len = nit->first - pit->first;
                G[*p].push_back({*np, len});
                G[*np].push_back({*p, len});
            }

            // update segments
            for (; it != tit; it++)
                if (it->end == 1) mp.erase(it->y);
        }
    }();

    auto clean = [&](int which) {
        // onl
        vi *v = &R[which].onl;
        std::sort(v->begin(), v->end(), [&](int i, int j) { return ind2[i].second < ind2[j].second; });
        v->erase(std::unique(v->begin(), v->end()), v->end());
        for (int i = 0; i + 1 < v->size(); i++) {
            int low = v->at(i), high = v->at(i + 1);
            int len = ind2[high].second - ind2[low].second;
            G[low].push_back({high, len});
            G[high].push_back({low, len});
        }

        // onr
        v = &R[which].onr;
        std::sort(v->begin(), v->end(), [&](int i, int j) { return ind2[i].second < ind2[j].second; });
        v->erase(std::unique(v->begin(), v->end()), v->end());
        for (int i = 0; i + 1 < v->size(); i++) {
            int low = v->at(i), high = v->at(i + 1);
            int len = ind2[high].second - ind2[low].second;
            G[low].push_back({high, len});
            G[high].push_back({low, len});
        }

        // onb
        v = &R[which].onb;
        std::sort(v->begin(), v->end(), [&](int i, int j) { return ind2[i].first < ind2[j].first; });
        v->erase(std::unique(v->begin(), v->end()), v->end());
        for (int i = 0; i + 1 < v->size(); i++) {
            int low = v->at(i), high = v->at(i + 1);
            int len = ind2[high].first - ind2[low].first;
            G[low].push_back({high, len});
            G[high].push_back({low, len});
        }

        // ont
        v = &R[which].ont;
        std::sort(v->begin(), v->end(), [&](int i, int j) { return ind2[i].first < ind2[j].first; });
        v->erase(std::unique(v->begin(), v->end()), v->end());
        for (int i = 0; i + 1 < v->size(); i++) {
            int low = v->at(i), high = v->at(i + 1);
            int len = ind2[high].first - ind2[low].first;
            G[low].push_back({high, len});
            G[high].push_back({low, len});
        }
    };

    for (int i = 1; i <= n + 2; i++) clean(i);

    int s = ind[{R[n + 1].l, R[n + 1].b}];
    int e = ind[{R[n + 2].l, R[n + 2].b}];

    std::vector<ll> dis(G.size(), 1e18);
    vi vis(G.size(), false);
    dis[s] = 0;

    std::priority_queue<pil, vpil, std::greater<pil>> pq;
    pq.push({0, s});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (vis[u]) continue;
        vis[u] = true;

        for (auto &[v, len] : G[u]) {
            if (vis[v]) continue;
            if (dis[v] > dis[u] + len) {
                dis[v] = dis[u] + len;
                pq.push({dis[v], v});
            }
        }
    }

    if (dis[e] == 1e18) {
        std::cout << "No Path\n";
    } else {
        std::cout << dis[e] << '\n';
    }
    [&] { // clear!!
        G.clear();
        ind.clear();
        ind2.clear();
        index = 0;
        for (int i = 1; i <= n + 2; i++) {
            R[i].onl.clear();
            R[i].onr.clear();
            R[i].ont.clear();
            R[i].onb.clear();
        }
    }();
}

int main() {
    int T;
    std::cin >> T;
    while (T--) run();
}