Illuminations - 题解
标签与难度
标签: 计算几何, 凸包, 贪心算法, 倍增 (Binary Lifting), 区间覆盖问题, 构造 难度: 2300
题目大意喵~
你好呀，指挥官！这次的任务是关于照明的~
我们有一个凸多边形，它有 个顶点。在多边形外面，有 个可以安装照明灯的位置。每一盏灯都能照亮多边形外缘的一部分。
我们的目标是，用最少数量的灯，把多边形的整个外缘都照亮。同时，我们还需要给出一个可行的安装方案，也就是告诉大家要用哪些灯，喵~
输入会给我们多边形的 个顶点坐标和 个灯的坐标。输出就是最少需要的灯数，以及这些灯的编号。
解题思路分析
这道题看起来像是一道几何题，但它的核心其实是一个非常经典的算法问题——区间覆盖问题，只不过披上了一层几何的外衣，而且还是在一个环上，喵~
让我来一步步拆解这个问题，把它变成我们熟悉的样子吧！
第一步：把几何问题转化为区间问题
首先，我们得弄明白一盏灯能照亮多边形的哪一部分。
想象一下，你站在多边形外的一个点（灯的位置）上，看着这个凸多边形。你的视线会被多边形本身挡住，但你能看到它的一部分轮廓。你能看到的最左边和最右边的点，就是从你的位置到多边形的两条切线与多边形的切点。
这两个切点之间的多边形边界，就是这盏灯能照亮的范围。因为这是个凸多边形，所以切点一定是多边形的某个顶点。
所以，对于每一个灯，我们都可以计算出它能照亮的顶点范围。比如说，第 盏灯能照亮从顶点 到顶点 的所有边（逆时针方向）。这样，几何问题就成功转化成了一个区间覆盖问题：我们有 个区间 ，要用最少的区间覆盖掉所有的 个顶点。
怎么找切点呢？ 这是一个计算几何中的经典问题。对于一个凸多边形和一个外部点 ，我们可以用一种类似二分搜索的方法在 的时间内找到两个切点。这个技术通常叫做“求凸多边形关于某一方向的极点”。我们不需要自己从零实现，可以直接使用计算几何模板里的 tangent 函数，它能帮我们搞定这一切，喵~
第二步：处理环形上的区间覆盖
现在问题变成了：在一个由 个顶点组成的环上，我们有 个覆盖区间，求最少需要多少个区间才能完全覆盖整个环。
环形的问题通常比线性问题要麻烦一点，因为有“绕圈”的情况。一个经典的解决策略是断环为链，然后加倍！
我们可以把多边形的顶点序列 复制一份，变成 ，其中 和 是同一个点。
- 一个普通的覆盖区间 (其中 ) 在这个新链上就对应两个区间： 和 。
- 一个跨越了 和 的“环绕”区间 (其中 ) 在新链上就对应一个长区间 。
现在，我们的目标变成了：从某个起点 开始，用最少的区间覆盖住长度为 的一段，也就是覆盖 。因为我们不知道从哪个顶点开始覆盖是最好的，所以我们需要对每个可能的起点 都计算一次，然后取最小值。
第三步：贪心策略与倍增优化
对于一个固定的起点 ，要覆盖线性区间 ，我们可以使用贪心策略：
- 当前已经覆盖到了位置
current_pos（初始时current_pos = i）。 - 在所有能够覆盖
current_pos的区间里，选择一个能延伸到最远位置的区间。 - 更新
current_pos为这个最远的位置。 - 重复上述步骤，直到
current_pos超过或等于 。
但是，对每个起点都跑一遍这个贪心还是太慢了。我们需要更快的办法！
注意到，从任何一个点 p 出发，我们总是会选择跳到最远的那个点。这个“最远的点”是可以预处理的。
我们定义一个数组 max_reach[p]，表示从不超过 p 的位置开始的所有区间中，能到达的最远的点。
- 初始化
max_reach[p] = p。 - 对于每个灯覆盖的区间 ，我们更新
max_reach[s] = max(max_reach[s], e)。 - 然后，我们进行一次传递：
for p from 1 to 2n-1，max_reach[p] = max(max_reach[p], max_reach[p-1])。这样max_reach[p]就真正代表了从 或 之前的位置出发，一步能跳到的最远的地方。
现在，我们的贪心策略变成了：从 p 跳到 max_reach[p]。这是一个固定的转移关系！我们要做的就是，从起点 i 开始，最少跳多少次才能到达或超过 i+n-1。
这个问题，就是倍增（Binary Lifting） 的主场啦！
我们可以预处理一个 jump[p][k] 数组，表示从点 p 开始，连续跳 次能到达的位置。
- 基础情况:
jump[p][0] = max_reach[p](跳 次)。 - 递推关系:
jump[p][k] = jump[ jump[p][k-1] ][k-1](从p跳 次，等于从p跳 次，再从落点跳 次)。
这个预处理需要 的时间。
第四步：整合求解
有了倍增数组，对于任何一个起点 i，我们可以在 的时间内找到答案：
- 设当前位置
pos = i，步数steps = 0。 - 从大到小遍历
k(比如从 19 到 0)。 - 如果
jump[pos][k]还到不了终点i+n-1，说明这个大跳是安全的，我们可以跳！pos = jump[pos][k]steps += (1 << k)
- 循环结束后，
pos就在终点前一步的位置，我们再跳最后一次 (jump[pos][0]) 就肯定能到达终点。所以总步数是steps + 1。
我们对所有 都这么计算一遍，找到最小的步数和对应的起点。
如何输出方案呢？ 在预处理 max_reach 数组时，我们不仅记录最远能到哪，还要记录是哪一盏灯实现了这次跳跃。我们可以用另一个数组 illuminant_id[p] 来存。之后，根据找到的最佳起点，模拟一遍贪心跳跃过程，每次记录下 illuminant_id[pos]，就能得到方案啦！
总结一下我们的完整计划：
- 几何处理: 读入数据，求凸包，确保顶点是逆时针的。
- 区间转化: 对 个灯，用
tangent函数求出它们各自覆盖的顶点区间 。 - 线性化: 将环上的顶点和区间扩展到 的链上。
- 贪心预处理: 计算
max_reach[p]和illuminant_id[p]数组。 - 倍增预处理: 计算
jump[p][k]数组。 - 求解: 遍历所有可能的起点 ，用倍增快速计算最少步数，找到全局最优解。
- 构造答案: 根据最优起点，模拟贪心跳跃过程，输出使用的灯的编号。
这样一来，一个复杂的几何问题就被我们一步步分解，用贪心和倍增优雅地解决了，是不是很有趣呢，喵~
代码实现
这是我根据上面的思路，精心重构的一份代码，希望能帮助你理解呐~
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
// 使用 long long 来避免整数溢出，喵~
using ll = long long;
// 点/向量 结构体
struct Point {
ll x, y;
int id = 0; // 可以用来存顶点的原始编号
bool operator<(const Point& other) const {
if (x != other.x) return x < other.x;
return y < other.y;
}
};
// 向量减法
Point operator-(const Point& a, const Point& b) {
return {a.x - b.x, a.y - b.y};
}
// 叉积，用来判断方向
ll cross_product(Point a, Point b) {
return a.x * b.y - a.y * b.x;
}
// 凸包，这里只保留了我们需要的功能
struct ConvexPolygon {
std::vector<Point> p; // 逆时针存储的顶点
// 获取顶点i的下一个顶点索引
int next(int i) const { return (i + 1) % p.size(); }
// 寻找从外部点a出发的两条切线，返回切点在p中的索引
// 这是通过二分查找极点来实现的，复杂度 O(log n)
std::pair<int, int> find_tangents(const Point& a) const {
int n = p.size();
auto is_left_turn = [&](int i, const Point& dir) {
return cross_product(dir, p[next(i)] - p[i]) >= 0;
};
auto find_extreme = [&](const Point& dir) {
int l = 0, r = n - 1;
bool dir_at_0 = is_left_turn(0, dir);
if (dir_at_0 != is_left_turn(n - 1, dir)) {
while (l < r) {
int mid = l + (r - l) / 2;
if (is_left_turn(mid, dir) == dir_at_0) {
l = mid + 1;
} else {
r = mid;
}
}
return l;
} else {
while (l < r) {
int mid = l + (r - l) / 2;
if (cross_product(dir, p[mid] - p[0]) > 0) {
l = mid + 1;
} else {
r = mid;
}
}
if (is_left_turn(l, dir)) return l;
l = 0, r = n - 1;
while (l < r) {
int mid = l + (r - l + 1) / 2;
if (cross_product(dir, p[mid] - p[0]) < 0) {
r = mid - 1;
} else {
l = mid;
}
}
if (!is_left_turn(l, dir)) return l;
return 0;
}
};
// 从点a到多边形顶点的向量作为方向
int tan1_idx = find_extreme(p[0] - a);
int tan2_idx = find_extreme(a - p[0]);
// 确保 tangent1 是逆时针方向的第一个切点
if (cross_product(p[tan1_idx] - a, p[tan2_idx] - a) < 0) {
std::swap(tan1_idx, tan2_idx);
}
return {tan1_idx, tan2_idx};
}
};
// Andrew's Monotone Chain 算法求凸包
ConvexPolygon build_convex_hull(std::vector<Point>& points) {
int n = points.size();
if (n <= 2) return {points};
std::sort(points.begin(), points.end());
std::vector<Point> hull;
for (int i = 0; i < n; ++i) {
while (hull.size() >= 2 && cross_product(hull.back() - hull[hull.size()-2], points[i] - hull.back()) <= 0) {
hull.pop_back();
}
hull.push_back(points[i]);
}
for (int i = n - 2, t = hull.size() + 1; i >= 0; i--) {
while (hull.size() >= t && cross_product(hull.back() - hull[hull.size()-2], points[i] - hull.back()) <= 0) {
hull.pop_back();
}
hull.push_back(points[i]);
}
hull.pop_back(); // 最后一个点和第一个点重复了
return {hull};
}
const int MAX_LOG_N = 20;
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n_pts, m;
std::cin >> n_pts >> m;
std::vector<Point> initial_points(n_pts);
for (int i = 0; i < n_pts; ++i) {
std::cin >> initial_points[i].x >> initial_points[i].y;
}
ConvexPolygon poly = build_convex_hull(initial_points);
int n = poly.p.size();
if (n == 0) {
std::cout << (m > 0 ? "1\n1\n" : "0\n\n");
return 0;
}
// --- 核心算法开始 ---
// 1. 线性化 & 贪心预处理
int linear_size = 2 * n;
std::vector<int> max_reach(linear_size);
std::vector<int> source_illuminant(linear_size);
for (int i = 0; i < linear_size; ++i) {
max_reach[i] = i;
}
for (int i = 1; i <= m; ++i) {
Point light_pos;
std::cin >> light_pos.x >> light_pos.y;
auto tangents = poly.find_tangents(light_pos);
int u = tangents.first;
int v = tangents.second;
if (u <= v) {
// 普通区间
if (v > max_reach[u]) {
max_reach[u] = v;
source_illuminant[u] = i;
}
if (v + n > max_reach[u + n]) {
max_reach[u + n] = v + n;
source_illuminant[u + n] = i;
}
} else {
// 环绕区间
if (v + n > max_reach[u]) {
max_reach[u] = v + n;
source_illuminant[u] = i;
}
}
}
// 传递max_reach
for (int i = 1; i < linear_size; ++i) {
if (max_reach[i-1] > max_reach[i]) {
max_reach[i] = max_reach[i-1];
source_illuminant[i] = source_illuminant[i-1];
}
}
// 2. 倍增预处理
std::vector<std::vector<int>> jump(linear_size, std::vector<int>(MAX_LOG_N));
for (int i = 0; i < linear_size; ++i) {
jump[i][0] = max_reach[i];
}
for (int k = 1; k < MAX_LOG_N; ++k) {
for (int i = 0; i < linear_size; ++i) {
jump[i][k] = jump[jump[i][k-1]][k-1];
}
}
// 3. 寻找最优起点
int min_lights = m + 1;
int best_start_node = -1;
for (int i = 0; i < n; ++i) {
int current_pos = i;
int target_pos = i + n;
int steps = 0;
if (max_reach[current_pos] < target_pos) { // 检查是否可以覆盖
for (int k = MAX_LOG_N - 1; k >= 0; --k) {
if (jump[current_pos][k] < target_pos) {
current_pos = jump[current_pos][k];
steps += (1 << k);
}
}
// 还需要最后一次跳跃
steps++;
} else { // 一次就够了
steps = 1;
}
// 检查是否真的覆盖了
if (max_reach[current_pos] >= target_pos) {
if (steps < min_lights) {
min_lights = steps;
best_start_node = i;
}
}
}
// 4. 输出结果
if (best_start_node == -1) {
std::cout << -1 << std::endl;
} else {
std::cout << min_lights << std::endl;
int current_pos = best_start_node;
for (int i = 0; i < min_lights; ++i) {
std::cout << source_illuminant[current_pos] << (i == min_lights - 1 ? "" : " ");
current_pos = max_reach[current_pos];
}
std::cout << std::endl;
}
return 0;
}复杂度分析
时间复杂度:
- 读入 个点并建立凸包的时间复杂度是 ，其中 是初始点数。设凸包顶点数为 。
- 对 个灯，每个灯寻找切点需要 ，总共是 。
- 预处理
max_reach数组需要 。 - 预处理倍增的
jump数组需要 。 - 对 个可能的起点，每个用倍增计算需要 ，总共是 。
- 所以总的时间复杂度由以上几部分中最大的决定，就是 ，非常高效！
空间复杂度:
- 存储凸包顶点需要 。
max_reach和source_illuminant数组需要 。- 倍增的
jump数组需要 的空间。 - 所以空间复杂度主要由倍增表决定。
知识点总结
这道题是多种算法思想的美妙结合，喵~
- 问题转化: 能够识别出问题的本质，将复杂的几何设定转化为经典的算法模型（区间覆盖）是解题的第一步，也是最重要的一步！
- 计算几何基础: 了解凸包的性质，知道如何求凸包以及如何从外部点找凸包的切线。这些都是计算几何工具箱里的常备工具。
- 环形问题处理: “断环为链，长度加倍”是处理环形数组/序列问题的通用技巧，非常实用。
- 贪心算法: 在确定了覆盖方向后，每次都选择能延伸最远的区间，是解决区间覆盖问题的标准贪心思路。
- 倍增 (Binary Lifting): 当我们有一个固定的“跳跃”关系（比如从
p跳到max_reach[p]），并且需要求最少跳多少次才能到达某个目标时，倍增就是进行加速的绝佳武器。它能把线性的模拟过程优化到对数级别。
希望这篇题解能帮到你，如果还有其他问题，随时可以来问我哦，喵~！