「POI2010」灯 Lamp 题解

直接说难点和注意事项：

开区间处理：窗户是开矩形，光线在边界上被吸收。代码中使用 x1 + EPS < x2 等严格不等式判断交集，确保边界点不会被错误计入。

浮点精度：使用 EPS = 1e-12 处理浮点比较，避免因精度问题导致的误判。

集合爆炸：每次迭代矩形数量可能增长，代码设置了 MAX_RECTS = 200000 作为上限，防止内存溢出。实际数据中矩形数量不会达到此上限。

反射次数上限：T_MAX = 2000 足以覆盖所有有效光路。随着反射次数增加，等效距离变大，区域会迅速收缩，更多次反射不会产生新的有效路径。

code:

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

using namespace std;

const double D = 10.0;               // 两建筑物之间的距离
const int T_MAX = 2000;              // 最大反射次数
const double EPS = 1e-12;            // 浮点比较精度
const double AREA_EPS = 1e-12;       // 面积最小值
const int MAX_RECTS = 200000;        // 矩形数量上限

// 开矩形结构体
struct Rect {
    double x1, x2, y1, y2;
    Rect(double x1 = 0, double x2 = 0, double y1 = 0, double y2 = 0)
        : x1(x1), x2(x2), y1(y1), y2(y2) {}

    // 判断两个开矩形是否有交集（有内点）
    bool intersects(const Rect& other) const {
        return x1 + EPS < other.x2 && other.x1 + EPS < x2 &&
               y1 + EPS < other.y2 && other.y1 + EPS < y2;
    }

    // 计算两个开矩形的交集（仍为开矩形）
    Rect intersection(const Rect& other) const {
        double nx1 = max(x1, other.x1);
        double nx2 = min(x2, other.x2);
        double ny1 = max(y1, other.y1);
        double ny2 = min(y2, other.y2);
        return Rect(nx1, nx2, ny1, ny2);
    }

    // 判断矩形是否有效（宽度和高度为正）
    bool valid() const {
        return x1 + EPS < x2 && y1 + EPS < y2;
    }

    // 计算矩形面积
    double area() const {
        return (x2 - x1) * (y2 - y1);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<Rect> B(n), C(m);
    for (int i = 0; i < n; ++i) {
        double x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        B[i] = Rect(x1, x2, y1, y2);
    }
    for (int i = 0; i < m; ++i) {
        double x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        C[i] = Rect(x1, x2, y1, y2);
    }

    // 初始 S：所有 C 窗户缩放 1/D，对应第一个反射点 p1 的取值范围
    vector<Rect> S;
    for (const Rect& c : C) {
        S.emplace_back(c.x1 / D, c.x2 / D, c.y1 / D, c.y2 / D);
    }

    vector<bool> illuminated(n, false);
    int t = 1;

    while (t <= T_MAX && !S.empty()) {
        // 偶数次反射：检查能否照射到 B 窗户
        if (t % 2 == 0) {
            for (int i = 0; i < n; ++i) {
                if (illuminated[i]) continue;
                Rect b_scaled(B[i].x1 / (t * D), B[i].x2 / (t * D),
                              B[i].y1 / (t * D), B[i].y2 / (t * D));
                for (const Rect& r : S) {
                    if (r.intersects(b_scaled)) {
                        illuminated[i] = true;
                        break;
                    }
                }
            }
        }

        // 确定下一反射点的窗户类型（奇数次反射后为 B 窗，偶数次后为 C 窗）
        vector<Rect>& next_windows = (t % 2 == 1) ? B : C;
        double scale = 1.0 / ((t + 1) * D);   // 缩放因子
        vector<Rect> S_new;

        for (const Rect& r : S) {
            for (const Rect& w : next_windows) {
                Rect w_scaled(w.x1 * scale, w.x2 * scale,
                              w.y1 * scale, w.y2 * scale);
                if (r.intersects(w_scaled)) {
                    Rect inter = r.intersection(w_scaled);
                    if (inter.valid() && inter.area() > AREA_EPS) {
                        S_new.push_back(inter);
                    }
                }
            }
        }

        if (S_new.empty()) break;
        if (S_new.size() > MAX_RECTS) break;   // 矩形数量过多，提前终止
        S = move(S_new);
        ++t;
    }

    // 收集结果并输出
    vector<int> ans;
    for (int i = 0; i < n; ++i) {
        if (illuminated[i]) ans.push_back(i + 1);
    }
    cout << ans.size() << '\n';
    for (size_t i = 0; i < ans.size(); ++i) {
        if (i > 0) cout << ' ';
        cout << ans[i];
    }
    cout << endl;

    return 0;
}

时间复杂度：$O(T × R × 600)$（最坏）（当然实际运行中，由于区域不断收缩，R保持在较小水平，远优于理论最坏情况）

空间复杂度：$O(R)$