JumpingPoints - 题解

标签与难度

标签: 计算几何, 凸包, 最短路, 贪心, Funnel Algorithm 难度: 2200

题目大意喵~

你好呀，指挥官！阿波罗同学遇到了一个几何难题，需要我们帮忙呢，喵~

题目是这样的：在二维平面上，有 $N$ 条竖直的线段。第 $i$ 条线段的 $x$ 坐标固定为 $i$ ，它的 $y$ 坐标范围是 $[l_i, r_i]$ 。

我们的任务是，从第 $1$ 条到第 $N$ 条线段，每条线段上都选择一个点 $P_i = (i, y_i)$ ，其中 $l_i \le y_i \le r_i$ 。这样我们就得到了一个由 $N$ 个点组成的序列 $P_1, P_2, \dots, P_n$ 。

我们要让连接相邻点的路径总长度最短。这个总长度的计算公式是：

\text{Total Length} = \sum_{i=1}^{n-1} \text{dist}(P_i, P_{i+1})

其中 $\text{dist}(P_i, P_{i+1})$ 是点 $P_i$ 和 $P_{i+1}$ 之间的欧几里得距离。因为 $P_i$ 和 $P_{i+1}$ 的 $x$ 坐标分别是 $i$ 和 $i+1$ ，所以它们之间的距离就是：

\text{dist}(P_i, P_{i+1}) = \sqrt{((i+1) - i)^2 + (y_{i+1} - y_i)^2} = \sqrt{1 + (y_{i+1} - y_i)^2}

最后，我们需要输出我们选择的这 $N$ 个点的坐标，喵~

解题思路分析

喵哈哈，这个问题看起来就像是在一个由上下边界构成的“走廊”里找一条最短的路！要让路径最短，我们肯定希望它尽可能地“直”，对吧？就像把一根橡皮筋在两个点之间拉直一样，喵~

核心思想：绷紧的绳子

想象一下，所有下界点 $(i, l_i)$ 构成了一条下边界，所有上界点 $(i, r_i)$ 构成了一条上边界。我们要求的路径，就是从第1条线段上的某个点出发，到第 $N$ 条线段上的某个点结束，并且全程都不能超出这个上下边界构成的“走廊”。

最短的路径，一定是一条“绷紧”的路径。它要么是一条直线，要么会在碰到走廊边界的“凸角”时发生弯折。这些“凸角”就是我们路径上的关键转折点。

关键转折点

这条最短路径，它只会在必要的时候拐弯。什么时候是必要的时候呢？就是当路径前方的“视线”被走廊的某个边界点挡住的时候。这些挡住视线的点，就是路径的转折点，它们必然是某个 $(i, l_i)$ 或者 $(i, r_i)$ 。

那么，路径的起点和终点呢？我们可以通过一点点微扰分析（或者直觉！）猜到，最优路径的起点 $P_1$ 一定是 $(1, l_1)$ 或 $(1, r_1)$ ，终点 $P_n$ 一定是 $(n, l_n)$ 或 $(n, r_n)$ 。因为如果起点或终点在线段的中间，我们总可以稍微移动它来让连接它的那段路更“平”，从而缩短总长度，直到它碰到端点为止。

所以，问题就简化为：从 4 种可能的起终点组合中，找出最短的那条路径：

$(1, l_1) \to (n, l_n)$
$(1, l_1) \to (n, r_n)$
$(1, r_1) \to (n, l_n)$
$(1, r_1) \to (n, r_n)$

Funnel Algorithm (漏斗算法)

对于一个固定的起点和终点，我们怎么找出这条“绷紧”的路径呢？这里就要用到一个很酷的算法，叫做“漏斗算法”，喵~

我们可以从起点开始，贪心地走。在当前点，我们向前看，找到最远的一个我们能“直达”的边界点，然后直接走过去。这个过程就像我们的视线形成了一个“漏斗”，我们沿着漏斗的边缘前进。

具体实现是这样的：

我们维护两个点集，一个是由下边界点 (i, l_i) 构成的“上凸链”（从侧面看），另一个是由上边界点 (i, r_i) 构成的“下凸链”。这两个链条共同构成了我们的“漏斗”。
我们从当前路径的最后一个顶点（一开始是起点）出发，依次考察 $i=2, 3, \dots, n$ 的线段。
每考察一个新的线段 $i$ ，我们就用它的两个端点 $(i, l_i)$ 和 $(i, r_i)$ 来更新我们的漏斗。
在更新时，我们可能会发现，前方的下边界“侵入”了我们到上边界的视线，或者上边界“侵入”了到下边界的视线。
- 例如，如果点 $(i, l_i)$ 跑到了连接当前顶点和上边界链条的直线的“上方”，说明视线被上边界的一个点挡住了，路径必须在这里拐弯。这个上边界的点就是我们的下一个转折点。
- 反之亦然。
一旦找到一个转折点，我们就把它加入我们的路径顶点列表，然后以它为新的起点，继续这个过程，直到我们到达终点 $n$ 。

这个过程可以用两个双端队列（或者用数组模拟的栈）来高效实现，每次迭代，每个边界点最多只会被推入和弹出一次，所以对于固定的起终点，寻找路径的时间复杂度是 $O(N)$ 的，超快！

特殊情况

还有一个很简单但要考虑到的情况：如果所有线段的区间 [l_i, r_i] 有一个公共的交集，也就是说 max(l_i) $\le$ min(r_i)，那么我们就可以画一条水平直线穿过所有线段！这显然是最短的路径，它的总长度是 $n-1$ 。我们可以直接选择 $y_i = \max(l_i)$ 作为所有点的高度。

总结一下步骤

先检查是否存在一个公共交集。如果是，直接输出水平线路径。
如果不是，就枚举 4 种起终点组合。
对每种组合，使用漏斗算法计算出路径的转折点序列。
根据转折点序列，通过线性插值计算出所有 $P_i=(i, y_i)$ 的坐标。
计算这 4 条路径的总长度，选择最短的那一条作为我们的答案输出。

这样，我们就能帮阿波罗解决这个难题啦，喵~

代码实现

这是我根据上面的思路，精心重构的代码哦！注释写得很详细，希望能帮到你，喵~

cpp

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>

// 为了精确，我们用 long double，喵~
using LD = long double;

// 定义一个点结构体
struct Point {
    int x;
    LD y;
};

// 全局变量存储输入
int n;
std::vector<int> l, r;

// 叉积计算，判断点 c 在向量 ab 的哪一侧
// > 0: c 在 ab 左侧 (逆时针)
// < 0: c 在 ab 右侧 (顺时针)
// = 0: c 在 ab 线上
LD cross_product(Point a, Point b, Point c) {
    return (LD)(b.x - a.x) * (c.y - a.y) - (LD)(b.y - a.y) * (c.x - a.x);
}

// 计算两点间距离
LD distance(Point p1, Point p2) {
    LD dx = p1.x - p2.x;
    LD dy = p1.y - p2.y;
    return std::sqrt(dx * dx + dy * dy);
}

// 核心函数：使用漏斗算法计算给定起点和终点的最短路径
std::vector<Point> compute_path(LD y_start, LD y_end) {
    std::vector<Point> path_vertices;
    path_vertices.push_back({1, y_start});

    Point current_vertex = {1, y_start};
    
    // lower_chain 和 upper_chain 构成了我们的“漏斗”
    // lower_chain 是下边界，由 (i, l_i) 构成，它本身是一个上凸包
    // upper_chain 是上边界，由 (i, r_i) 构成，它本身是一个下凸包
    std::vector<Point> lower_chain, upper_chain;

    while (current_vertex.x < n) {
        lower_chain.clear();
        upper_chain.clear();
        lower_chain.push_back(current_vertex);
        upper_chain.push_back(current_vertex);

        Point next_vertex = {n, y_end};
        bool found_turn = false;

        for (int i = current_vertex.x + 1; i <= n; ++i) {
            Point p_lower = {i, (LD)(i == n ? y_end : l[i - 1])};
            Point p_upper = {i, (LD)(i == n ? y_end : r[i - 1])};

            // 检查下边界是否“侵入”了上方的视线
            if (upper_chain.size() > 1) {
                if (cross_product(upper_chain[0], upper_chain.back(), p_lower) > 0) {
                    next_vertex = upper_chain.back();
                    found_turn = true;
                    break;
                }
            }

            // 检查上边界是否“侵入”了下方的视线
            if (lower_chain.size() > 1) {
                 if (cross_product(lower_chain[0], lower_chain.back(), p_upper) < 0) {
                    next_vertex = lower_chain.back();
                    found_turn = true;
                    break;
                }
            }

            // 维护上边界的下凸性
            while (upper_chain.size() > 1 && cross_product(upper_chain[upper_chain.size() - 2], upper_chain.back(), p_upper) <= 0) {
                upper_chain.pop_back();
            }
            upper_chain.push_back(p_upper);

            // 维护下边界的上凸性
            while (lower_chain.size() > 1 && cross_product(lower_chain[lower_chain.size() - 2], lower_chain.back(), p_lower) >= 0) {
                lower_chain.pop_back();
            }
            lower_chain.push_back(p_lower);
        }

        path_vertices.push_back(next_vertex);
        current_vertex = next_vertex;
    }

    // 根据找到的转折点，通过线性插值生成完整的路径
    std::vector<Point> full_path;
    full_path.push_back(path_vertices[0]);
    for (size_t i = 0; i < path_vertices.size() - 1; ++i) {
        Point start_v = path_vertices[i];
        Point end_v = path_vertices[i+1];
        for (int x = start_v.x + 1; x <= end_v.x; ++x) {
            LD y = start_v.y + (end_v.y - start_v.y) * (x - start_v.x) / (end_v.x - start_v.x);
            full_path.push_back({x, y});
        }
    }
    return full_path;
}

void solve(int case_num) {
    std::cin >> n;
    l.assign(n, 0);
    r.assign(n, 0);
    int max_l = 0, min_r = 2000000001;
    for (int i = 0; i < n; ++i) {
        std::cin >> l[i] >> r[i];
        max_l = std::max(max_l, l[i]);
        min_r = std::min(min_r, r[i]);
    }

    std::cout << "Case #" << case_num << ":" << std::endl;

    // 特殊情况：存在公共交集，最短路径是水平线
    if (max_l <= min_r) {
        for (int i = 0; i < n; ++i) {
            std::cout << i + 1 << " " << max_l << std::endl;
        }
        return;
    }

    // 4种可能的起终点组合
    std::vector<std::pair<LD, LD>> endpoints;
    endpoints.push_back({(LD)l[0], (LD)l[n - 1]});
    endpoints.push_back({(LD)l[0], (LD)r[n - 1]});
    endpoints.push_back({(LD)r[0], (LD)l[n - 1]});
    endpoints.push_back({(LD)r[0], (LD)r[n - 1]});

    std::vector<Point> best_path;
    LD min_dist = -1.0;

    for (const auto& ep : endpoints) {
        std::vector<Point> current_path = compute_path(ep.first, ep.second);
        LD current_dist = 0;
        for (size_t i = 0; i < current_path.size() - 1; ++i) {
            current_dist += distance(current_path[i], current_path[i+1]);
        }

        if (min_dist < 0 || current_dist < min_dist) {
            min_dist = current_dist;
            best_path = current_path;
        }
    }

    for (const auto& p : best_path) {
        std::cout << p.x << " " << std::fixed << std::setprecision(6) << p.y << std::endl;
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    for (int i = 1; i <= t; ++i) {
        solve(i);
    }
    return 0;
}

复杂度分析

时间复杂度: $O(N)$ $O (N)$
- 对于特殊情况，我们只需要一次遍历来找到 max_l 和 min_r，复杂度是 $O(N)$ 。
- 对于一般情况，我们调用 compute_path 函数 4 次。在 compute_path 中，我们使用了漏斗算法。外层 while 循环的每次迭代都会使 current_vertex.x 增加，最多迭代 $N$ 次。内层的 for 循环和其中的 while 循环，每个边界点 (i, l_i) 和 (i, r_i) 最多被推入和弹出所在的凸包链一次。所以，compute_path 的总时间复杂度是 $O(N)$ 。总时间复杂度就是 $4 \times O(N) = O(N)$ 。
空间复杂度: $O(N)$ $O (N)$
- 我们需要 $O(N)$ 的空间来存储输入的 $l_i$ 和 $r_i$ 。
- 在 compute_path 函数中，lower_chain、upper_chain 和 path_vertices 最多存储 $N$ 个点，所以空间复杂度是 $O(N)$ 。

知识点总结

最短路思想: 认识到在有障碍（边界）的区域中，最短路径是“绷紧”的，这引导我们去寻找路径的转折点。
计算几何: 这个问题是计算几何中的经典模型——在简单多边形内求最短路。我们的“走廊”就是一个简单多边形。
Funnel Algorithm: 这是解决此类问题的标准高效算法。核心在于动态维护一个由视线构成的“漏斗”，并检测漏斗何时因被障碍物遮挡而收缩，从而找到路径的转折点。
凸包: 漏斗的两条边实际上是动态维护的凸包（一个上凸包，一个下凸包）。叉积是判断点与线段关系以及维护凸包性质的有力工具。
贪心: 算法的每一步都是在当前位置做出局部最优的选择（走到最远的可见点），最终得到全局最优解。

希望这篇题解能帮到你，如果还有不明白的地方，随时可以再来问我哦！喵~

JumpingPoints - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

核心思想：绷紧的绳子 ​

关键转折点 ​

Funnel Algorithm (漏斗算法) ​

特殊情况 ​

总结一下步骤 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​