题目分析

这是一个关于光线反射的几何问题。我们需要找出建筑物B中哪些窗户会被从原点发出的光线照射到，这些光线会在建筑物C的窗户上反射。

问题建模

1. 物理背景：光线从建筑物B的原点(0,0)发出，在建筑物C的窗户上反射，然后可能照射到建筑物B的窗户上。

2. 关键观察：由于两建筑物相距10米且墙面平行，可以将问题转化为在缩放坐标系中的矩形相交问题。

3. 算法思路：使用扫描线算法结合线段树来高效处理矩形的覆盖问题。

核心算法

扫描线 + 线段树：

1. 坐标缩放：对于反射次数k，将矩形坐标缩放1/k倍
2. 事件处理：将每个矩形的上下边界作为事件点
3. 线段树维护：使用线段树维护当前y坐标下x轴的覆盖情况
4. 结果收集：当覆盖数达到反射次数时，记录对应的窗户

代码实现

#include <iostream>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <string>
#include <list>
#include <deque>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <utility>
#include <sstream>
#include <cstring>
using namespace std;

#define FOR(I,A,B) for(int I=(A);I<=(B);I++)
#define FORD(I,A,B) for(int I=(A);I>=(B);I--)
#define REP(I,N) for(int I=0;I<(N);I++)
#define VAR(V,init) __typeof(init) V=(init)
#define FORE(I,C) for(VAR(I,(C).begin());I!=(C).end();I++)
#define CLR(A,v) memset((A),v,sizeof((A)))
#define ALL(X) (X).begin(),(X).end()
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SIZE(x) (int)(x.size())

const int max_r = 603;
const int max_e = 2610000;
const double eps = 1e-8;
#define MAX_H 1000

class rectangle {
public:
    double xl, yl, xu, yu;
    int id;

    rectangle() {}
    rectangle(double _xl, double _yl, double _xu, double _yu, int _id) :
        xl(_xl), yl(_yl), xu(_xu), yu(_yu), id(_id) {}

    void get(int _id) {
        scanf("%lf%lf%lf%lf", &xl, &yl, &xu, &yu);
        id = _id;
    }

    rectangle scale(double a) {
        return rectangle(xl * a, yl * a, xu * a, yu * a, id);
    }
};

inline bool is_zero(double x) {
    return -eps < x && x < eps;
}

class event {
public:
    double y;
    int x1, x2;
    int id;
    bool add;

    event() {}
    event(double _y, int _x1, int _x2, int _id, bool _add) :
        y(_y), x1(_x1), x2(_x2), id(_id), add(_add) {}

    bool operator<(const event &A) const {
        if (is_zero(A.y - y)) {
            return add < A.add;
        }
        return y < A.y;
    }
};

class tree {
public:
    int smax[max_e], all[max_e];
    PII win[max_r];
    set<PII> s;
    set<int> result;
    int N, O;

    void init(int _N, int _O) {
        O = _O;
        N = _N;
        while (N & (N - 1)) ++N;
        REP(i, N * 2) smax[i] = all[i] = 0;
        s.clear();
        result.clear();
    }

    void update_node(int a) {
        smax[a] = max(smax[2*a] + all[2*a], smax[2*a+1] + all[2*a+1]);
    }

    int find_max(int a) {
        if (a >= N) return a;
        if (smax[2*a] + all[2*a] == smax[a]) 
            return find_max(2*a);
        return find_max(2*a+1);
    }

    void add(int a, int b, int val, int id, bool recursive) {
        if (id != 0) {
            if (val > 0) {
                s.insert(MP(b, id));
                win[id] = MP(a, b);
            } else {
                if (!s.count(MP(b, id))) return;
                s.erase(MP(b, id));
            }
        }

        int va = a + N, vb = b + N;
        all[va] += val;

        while (va / 2 != vb / 2) {
            if (va % 2 == 0) all[va+1] += val;
            if (vb % 2 == 1) all[vb-1] += val;
            va /= 2; vb /= 2;
            update_node(va); update_node(vb);
        }

        while (va / 2 != 0) {
            va /= 2;
            update_node(va);
        }

        if (!recursive) return;

        while (smax[1] + all[1] == O) {
            int tmp = find_max(1) - N;
            PII x = *s.lower_bound(MP(tmp+1, 0));
            add(win[x.SE].FI, win[x.SE].SE, -1, x.SE, false);
            result.insert(x.SE);
            s.erase(x);
        }
    }
};

rectangle t[2][max_r];
event w[max_e];
tree T;
int n[2];

int convert(double x, const vector<double> &vd) {
    return lower_bound(ALL(vd), x) - vd.begin();
}

int main() {
    scanf("%d%d", &n[0], &n[1]);
    
    REP(i, 2) REP(j, n[i]) 
        t[i][j].get(j + 1);

    int pw = 2;
    rectangle R;
    set<int> result;

    while (pw < 1025) {
        int ec = 0;
        vector<double> v, vc;
        
        // 收集所有可能的x坐标
        FOR(k, 1, pw) {
            int pos = k % 2;
            REP(i, n[pos]) {
                v.PB(t[pos][i].xl / k);
                v.PB(t[pos][i].xu / k);
            }
        }
        
        sort(ALL(v));
        vc.PB(v[0]);
        FOR(i, 1, SIZE(v)-1)
            if (!is_zero(v[i] - vc.back()))
                vc.PB(v[i] + eps/2);

        double max_val = (double)MAX_H / pw;

        // 创建事件
        FOR(k, 1, pw) {
            int pos = k % 2;
            REP(i, n[pos]) {
                R = t[pos][i].scale(1.0/k);
                
                if (R.yl >= max_val || R.xu <= -max_val || max_val <= R.xl)
                    continue;
                    
                int a = convert(R.xl, vc), b = convert(R.xu, vc);
                w[ec] = event(R.yl, a, b, ((k==pw)?R.id:0), true);
                ++ec;
                w[ec] = event(R.yu, a, b, ((k==pw)?R.id:0), false);
                ++ec;
            }
        }

        sort(w, w + ec);
        T.init(SIZE(vc), pw);
        
        REP(i, ec) {
            T.add(w[i].x1, w[i].x2, (w[i].add?1:-1), w[i].id, true);
        }

        FORE(e, T.result) result.insert(*e);
        pw *= 2;
    }

    printf("%d\n", SIZE(result));
    FORE(e, result) printf("%d ", *e);
    puts("");

    return 0;
}

算法分析

时间复杂度

• 坐标处理：$O((n+m)\log(n+m))$
• 扫描线算法：$O((n+m)\log(n+m))$
• 总体复杂度：$O((n+m)\log(n+m))$

空间复杂度

• 需要 $O(n+m)$ 的额外空间存储事件和线段树

总结

解题关键：

1. 将光线反射问题转化为几何覆盖问题
2. 使用坐标缩放处理不同反射次数
3. 扫描线算法高效处理矩形覆盖

技巧亮点：

• 线段树维护区间覆盖
• 离散化处理浮点坐标
• 事件驱动扫描线

这种将物理问题转化为计算几何问题的方法，在处理光线追踪、反射等问题时非常有效。