「POI2014 R3」太阳灯 Solar lamps 题解

题目大意

有 $n$ 盏太阳能灯，每盏灯有一个位置 $(x_i, y_i)$。所有灯的照射区域是由两条射线围成的一个扇形区域，这两条射线由向量 $(X_1, Y_1)$ 和 $(X_2, Y_2)$ 定义。

灯的亮起规则：

• 在时刻 $i$，第 $i$ 盏灯会被通电亮起
• 如果一盏灯被至少 $k_i$ 盏其他亮着的灯照射到，它也会亮起
• 需要求出每盏灯第一次亮起的时刻

问题分析

关键难点

1. 几何判断：需要快速判断一盏灯是否在另一盏灯的照射范围内
2. 时间依赖：灯的亮起具有传递性，需要按时间顺序模拟
3. 大规模数据：$n \leq 200000$，需要高效算法

几何转换

对于灯 $A$ 和灯 $B$，$B$ 在 $A$ 的照射范围内当且仅当向量 $\overrightarrow{AB}$ 在由 $\overrightarrow{(X_1, Y_1)}$ 和 $\overrightarrow{(X_2, Y_2)}$ 张成的扇形区域内。

数学上，这等价于：

• $\overrightarrow{(X_1, Y_1)} \times \overrightarrow{AB} \geq 0$
• $\overrightarrow{AB} \times \overrightarrow{(X_2, Y_2)} \geq 0$

算法思路

方法一：直接模拟（适用于小数据）

对于 $n \leq 1000$ 的情况，可以直接模拟整个过程：

vector<bool> lit(n + 1, false);
for (int time = 1; time <= n; time++) {
    lit[time] = true;  // 通电亮起
    ans[time] = min(ans[time], time);
    
    bool changed;
    do {
        changed = false;
        for (int i = 1; i <= n; i++) {
            if (lit[i]) continue;
            
            int cnt = 0;
            for (int j = 1; j <= n; j++) {
                if (lit[j] && i != j) {
                    Point vec = lamps[i] - lamps[j];
                    if (inSector(vec)) {
                        cnt++;
                        if (cnt >= k[i]) break;
                    }
                }
            }
            
            if (cnt >= k[i]) {
                lit[i] = true;
                ans[i] = min(ans[i], time);
                changed = true;
            }
        }
    } while (changed);
}

复杂度：$O(n^3)$ 最坏情况，但实际中循环次数有限

方法二：极角排序 + 扫描线（适用于大数据）

步骤1：坐标变换

通过旋转坐标系，将照射区域变换到标准位置（如第一象限），简化几何判断。

步骤2：极角排序

将所有灯的位置按极角排序，建立角度到索引的映射：

vector<Point> points;
for (int i = 1; i <= n; i++) {
    points.push_back(lamps[i]);
    points.back().id = i;
}
sort(points.begin(), points.end());  // 按极角排序

步骤3：构建数据结构

使用树状数组（Fenwick Tree）来快速统计角度区间内的灯数量：

struct Fenwick {
    vector<int> tree;
    int n;
    
    Fenwick(int size) { n = size; tree.resize(n + 1, 0); }
    
    void update(int idx, int delta) {
        while (idx <= n) {
            tree[idx] += delta;
            idx += idx & -idx;
        }
    }
    
    int query(int idx) {
        int sum = 0;
        while (idx > 0) {
            sum += tree[idx];
            idx -= idx & -idx;
        }
        return sum;
    }
};

步骤4：时间扫描

按时间顺序处理每盏灯的通电：

vector<bool> activated(n + 1, false);
Fenwick fenw(n);

for (int time = 1; time <= n; time++) {
    int current = time;
    
    // 激活当前灯
    activated[current] = true;
    fenw.update(pos[current], 1);  // pos[current] 是排序后的位置
    
    // 对于每盏未激活的灯，检查其照射区间内的灯数量
    for (int i = 1; i <= n; i++) {
        if (activated[i]) continue;
        
        // 计算灯i的照射区间 [L, R]
        pair<int, int> interval = getInterval(i);
        int count = fenw.rangeQuery(interval.first, interval.second);
        
        if (count >= k[i]) {
            activated[i] = true;
            fenw.update(pos[i], 1);
            ans[i] = min(ans[i], time);
        }
    }
}

关键实现细节

1. 几何判断优化

bool inSector(const Point &p) {
    ll cross1 = dir1.cross(p);
    ll cross2 = p.cross(dir2);
    return cross1 >= 0 && cross2 >= 0;
}

2. 极角排序比较函数

bool polarCompare(const Point &a, const Point &b) {
    if (a.y == 0 && a.x > 0) return true;
    if (b.y == 0 && b.x > 0) return false;
    if (a.y > 0 && b.y < 0) return true;
    if (a.y < 0 && b.y > 0) return false;
    return a.cross(b) > 0;
}

3. 照射区间计算

对于每盏灯 $i$，其照射区间是极角排序后的一个连续区间 $[L_i, R_i]$，包含所有在其照射范围内的灯。

复杂度分析

直接模拟

• 时间复杂度：$O(n^3)$ 最坏情况
• 空间复杂度：$O(n)$
• 适用情况：$n \leq 1000$

极角排序 + 扫描线

• 预处理：$O(n \log n)$ 用于排序
• 每次查询：$O(\log n)$ 使用树状数组
• 总体复杂度：$O(n^2 \log n)$ 最坏情况
• 优化后：通过批量处理可达到 $O(n \log n)$

样例分析

以题目样例为例：

输入：

5
3 1 1 3
2 1
1 4
3 4
5 6
5 2
1 2 1 3 2

执行过程：

1. 时刻1：灯1通电亮起
   • 灯3被灯1照亮，满足 $k_3 = 1$，亮起
2. 时刻2：灯2通电亮起
   • 灯4被灯1、2、3照亮，满足 $k_4 = 3$，亮起
3. 时刻5：灯5通电亮起

输出：1 2 1 2 5

优化策略

1. 批量处理

使用优先队列来批量处理可能被点亮的灯，避免每次扫描所有灯。

2. 角度离散化

将连续的角度区间离散化为整数索引，便于使用树状数组。

3. 区间合并

对于照射区间相同的灯，可以批量处理。

4. 并行检查

使用多指针技术同时检查多个灯的照射条件。

完整代码框架

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXN = 200005;

struct Point {
    ll x, y;
    int id;
    // 几何运算...
};

// 几何判断函数
bool inSector(const Point &p);
bool polarCompare(const Point &a, const Point &b);

// 树状数组
struct Fenwick {
    // 实现...
};

int main() {
    // 读入数据
    
    if (n <= 1000) {
        // 小数据直接模拟
        directSimulation();
    } else {
        // 大数据使用几何优化
        geometricSolution();
    }
    
    // 输出结果
    return 0;
}

总结

这道题结合了计算几何和数据结构，主要考察：

1. 几何关系的理解和处理
2. 极角排序的应用
3. 树状数组/线段树在区间统计中的应用
4. 事件驱动模拟的技巧