多边形的“奇妙”

YU_QE · 2025-12-11 16:43:21 · 题解

看到这个多边形，这个题目却只给你点，我们要想想该怎么连边。注意到，每个多边形的点都是直角的顶点。什么意思？就是只有纵坐标和横坐标相等才可以连边。

• 怎么方便地连边？先离散化，每个点都对应一个编号，类似地，每个询问也进行离散化。规定 (x_1, y_1), \dots, (x_P, y_P) 是多边形的点。(x_{P+1},y_{P+1}), \dots, (x_{P + N}, y_{P + N}) 为询问点的起始点。(x_{P + N + 1}, y_{P+N+1}), \dots, (x_{P + 2N}, y_{P + 2N}) 为询问的结束点。可以把它们全部放进 map，横坐标的下标里面放纵坐标，纵坐标同理。这时候，让 map 里面套 set，既可以去重又可以排序。
• 之后，我们遍历 map，取出 set 来，设 i 一开始为 set 的开头，我们让 i 移动到第一个多边形的点，再加入 j 移动到下一个多边形的点，让 i 和 j 之间的节点两两之间连边，就可以保证多边形的点一定连到边，询问的点顺带也处理了。然后，我们递归遍历这张图，得出一个 DFN 序。破环成链，我们展开时 2 倍扩展这个 DFN 序列。然后做一个前缀和，S_i 为 DFN 为小于等于 i 的前缀和，每次令 S_i \gets S_{i-1} + D_i，D_i 为 DFN 为 i 的点与 i - 1 点的距离。
• 找到询问的起始点和询问点。设 x 为起始点，y 为结束点。假设 x 的 DFN 大于 y 的 DFN（如果不是可以交换）。现在设 C 为最大的 DFN（2 倍的原因），如果 S_x - S_y < S_{y+C} - S_x，差分标记 y 到 x 的区间，S_x - S_y > S_{y+C} - S_x，差分标记 x 到 y + C 的区间。简单来说，就是看看哪一个距离小，看看顺着走还是逆着走。

这是一道比较难的几何题。时间复杂度为 \mathcal{O}((N + P) \log^2 (N + P) + N + P)。

#include <bits/stdc++.h>
typedef long long ll;
constexpr int N = 1e6 + 10;
using namespace std;
int n, p;
map<int, set<int>> xt; // x 坐标对应的 y 坐标
map<int, set<int>> yt; // y 坐标对应的 x 坐标
map<pair<int, int>, int> idx;
// 离散化编号 
pair<int, int> P[N];
// 所有点的坐标
ll lst[N], sum[N]; // 前缀和&差分数组
int dfn[N], cnt; // dfn 序。
int h[N]; // dfn 对应的编号，也是序列
vector<int> g[N]; 
void add(int x, int y) {
    g[x].push_back(y);
    g[y].push_back(x);
}
void dfs(int x) {
    dfn[x] = ++cnt;
    h[cnt] = x;
    for (const auto &y : g[x]) {
        if (dfn[y]) continue;
        dfs(y);
    } 
} 
int main() {
    cin >> n >> p;
    for (int i = 1; i <= p; ++i) {
        int x, y;
        cin >> x >> y;
        xt[x].insert(y);
        yt[y].insert(x);
        idx[{x, y}] = i;
        P[i] = {x, y};
    }
    // 把多边形的点和询问放在一起，方便处理
    for (int i = 1; i <= n; ++i) {
        int sx, sy, ex, ey;
        cin >> sx >> sy >> ex >> ey;
        P[i + p] = {sx, sy};
        P[i + p + n] = {ex, ey};
        if (!idx[{sx, sy}]) {
            idx[{sx, sy}] = i + p;
            xt[sx].insert(sy);
            yt[sy].insert(sx);
        } 
        if (!idx[{ex, ey}]) {
            idx[{ex, ey}] = i + p + n; 
            xt[ex].insert(ey);
            yt[ey].insert(ex);
        }
    }
    // 横坐标加边
    for (auto &it : xt) {
        int x = it.first;
        auto i = xt[x].begin();
        while (i != xt[x].end()) {
            for (; i != xt[x].end(); ++i) if (idx[{x, *i}] <= p) break;
            auto j = next(i), k = i;
            for (; j != xt[x].end(); ++j) if (idx[{x, *j}] <= p) break;
            if (j == xt[x].end()) break;
            for (; k != j; ++k) add(idx[{x, *k}], idx[{x, *next(k)}]);
            i = next(j);
        }
    }
    // 纵坐标加边
    for (auto &it : yt) {
        int y = it.first;
        auto i = yt[y].begin();
        while (i != yt[y].end()) {
            for (; i != yt[y].end(); ++i) if (idx[{*i, y}] <= p) break;
            auto j = next(i), k = i;
            for (; j != yt[y].end(); ++j) if (idx[{*j, y}] <= p) break;
            if (j == yt[y].end()) break;
            for (; k != j; ++k) add(idx[{*k, y}], idx[{*next(k), y}]);
            i = next(j);
        }
    }
    dfs(1);
    for (int i = cnt + 1; i <= 2 * cnt; ++i) {
        h[i] = h[i - cnt]; // 破环成链，2 倍
    }
    for (int i = 1; i <= cnt * 2; ++i) {
        // int dis = 0;
        ll dis = abs(P[h[i]].first - P[h[i - 1]].first) + abs(P[h[i]].second - P[h[i - 1]].second); 
        sum[i] = sum[i - 1] + dis;
    }
    for (int i = 1; i <= n; ++i) {
        int x = dfn[idx[P[p + i]]], y = dfn[idx[P[p + i + n]]];
        if (x < y) swap(x, y); // 要保证 x 的 dfn > y 的 dfn 
        ll a = sum[x] - sum[y];
        ll b = sum[y + cnt] - sum[x];
        // 看看是否是正着走还是逆着走
        if (a < b) lst[y] += 1, lst[x + 1] -= 1; 
        else lst[x] += 1, lst[y + cnt + 1] -= 1; 
    } 
    for (int i = 1; i <= cnt * 2; ++i) lst[i] += lst[i - 1];
    for (int i = 1; i <= p; ++i) {
        int x = dfn[idx[P[i]]]; // 注意这里是 dfn 
        int w = lst[x] + lst[x + cnt];
        cout << w << '\n';
    }
    return 0;
} 

Link

感谢你用心看完。