光线追踪

GitHub跳转原题关系图 Canvas 关系图返回列表

枚举反射线段的内部整点，按水平线和竖直线有序维护最近碰撞点。

OJ: shumeng

题目 ID: CSP202206D

难度:提高+/省选-

标签:模拟扫描线有序集合几何

日期: 2026-07-31 16:21

形式化题目

平面内动态插入、删除 45 度角摆放的反射线段，每条线段有反射折损系数 $a$ 。有若干查询：从整数点 $(x,y)$ 以水平或竖直方向发射强度 $I$ 的光线，移动 $t$ 时刻后输出最终位置与取整后的强度；强度小于 1 时输出 0 0 0。

思路

光线从整数点沿坐标轴移动，45 度线段与它的交点也必然是整数点，因此可以把问题退化到一维坐标上处理。

只维护线段内部整点

把每条 45 度线段的内部整点全部枚举出来：

按 $y$ 分组，维护每个水平方向上的点集；
按 $x$ 分组，维护每个竖直方向上的点集。

只维护内部点可以自动排除端点（题目约定反射面不含端点）。每个点记录它属于哪条线段，删除线段时只需把它的所有点移除。

用有序集合找最近碰撞点

查询时光线沿某个方向移动，从对应直线（水平线或竖直线）的有序集合里用 upper_bound / lower_bound 找运动方向上的最近点：

向右找 y 固定的集合中第一个大于 $x$ 的点；
向左找 y 固定的集合中最后一个小于 $x$ 的点；
向上、向下同理在 x 固定的集合中查找。

反射与折损

碰撞后强度乘以该线段的折损系数 $a$ ，方向按斜率反射：

斜率 $+1$ ：方向映射为 $0\leftrightarrow 1$ 、 $2\leftrightarrow 3$ ；
斜率 $-1$ ：方向映射为 $0\leftrightarrow 3$ 、 $1\leftrightarrow 2$ 。

由于 $a\le 0.8$ 且 $I\le 10^9$ ，单次查询的碰撞次数很少；强度降到 1 以下就立即结束。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:40
 */
#include <bits/stdc++.h>
using namespace std;

// 一个 45 度反射面，由两个整数端点确定，方向为斜率 ±1
struct Segment {
    long long x1, y1, x2, y2; // 两个端点
    double loss;              // 反射折损系数 a
    int slope;                // 斜率：1 或 -1
    vector<pair<long long, long long> > point; // 线段内部所有整点
};

int operation_count;
vector<Segment> segment;                                    // 线段表，下标对应操作编号
map<long long, set<pair<long long, int> > > horizontal;     // 按 y 分组，保存 (x, 线段编号)
map<long long, set<pair<long long, int> > > vertical;       // 按 x 分组，保存 (y, 线段编号)

// 把线段内部的所有整点插入水平线和竖直线
void insert_segment(int id) {
    Segment &now = segment[id];
    long long length = llabs(now.x2 - now.x1);  // 线段内部点的个数 = 长度 - 1
    long long dx = now.x2 > now.x1 ? 1 : -1;
    long long dy = now.y2 > now.y1 ? 1 : -1;
    for (long long i = 1; i < length; i++) {
        long long px = now.x1 + dx * i;
        long long py = now.y1 + dy * i;
        now.point.push_back({px, py});
        horizontal[py].insert({px, id});
        vertical[px].insert({py, id});
    }
}

// 删除线段时，把它维护的所有内部整点从两条线上移除
void erase_segment(int id) {
    Segment &now = segment[id];
    for (int i = 0; i < (int)now.point.size(); i++) {
        horizontal[now.point[i].second].erase({now.point[i].first, id});
        vertical[now.point[i].first].erase({now.point[i].second, id});
    }
}

// 在方向 direction 上找从 (x,y) 出发最近的碰撞点。
// direction: 0 向右, 1 向上, 2 向左, 3 向下。找到返回 true 并回传距离和线段编号。
bool find_next(long long x, long long y, int direction, long long &distance, int &id) {
    if (direction == 0) {
        map<long long, set<pair<long long, int> > >::iterator line = horizontal.find(y);
        if (line == horizontal.end()) return false;
        set<pair<long long, int> >::iterator it = line->second.upper_bound({x, INT_MAX});
        if (it == line->second.end()) return false;
        distance = it->first - x;
        id = it->second;
        return true;
    }
    if (direction == 2) {
        map<long long, set<pair<long long, int> > >::iterator line = horizontal.find(y);
        if (line == horizontal.end()) return false;
        set<pair<long long, int> >::iterator it = line->second.lower_bound({x, -1});
        if (it == line->second.begin()) return false;
        --it;
        distance = x - it->first;
        id = it->second;
        return true;
    }
    if (direction == 1) {
        map<long long, set<pair<long long, int> > >::iterator line = vertical.find(x);
        if (line == vertical.end()) return false;
        set<pair<long long, int> >::iterator it = line->second.upper_bound({y, INT_MAX});
        if (it == line->second.end()) return false;
        distance = it->first - y;
        id = it->second;
        return true;
    }
    map<long long, set<pair<long long, int> > >::iterator line = vertical.find(x);
    if (line == vertical.end()) return false;
    set<pair<long long, int> >::iterator it = line->second.lower_bound({y, -1});
    if (it == line->second.begin()) return false;
    --it;
    distance = y - it->first;
    id = it->second;
    return true;
}

// 根据斜率计算反射后的新方向
int reflected_direction(int direction, int slope) {
    if (slope == 1) {
        int change[4] = {1, 0, 3, 2}; // 斜率 +1：左右互换，上下互换
        return change[direction];
    }
    int change[4] = {3, 2, 1, 0};     // 斜率 -1：水平变反向，垂直变反向
    return change[direction];
}

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

    cin >> operation_count;
    segment.resize(operation_count + 1);
    for (int operation = 1; operation <= operation_count; operation++) {
        int type;
        cin >> type;
        if (type == 1) {
            Segment now;
            cin >> now.x1 >> now.y1 >> now.x2 >> now.y2 >> now.loss;
            now.slope = (now.x2 - now.x1) * (now.y2 - now.y1) > 0 ? 1 : -1;
            segment[operation] = now;
            insert_segment(operation);
        } else if (type == 2) {
            int deleted;
            cin >> deleted;
            erase_segment(deleted);
        } else {
            long long x, y, time;
            double intensity;
            int direction;
            cin >> x >> y >> direction >> intensity >> time;
            // 逐次找最近碰撞点，直到时间用完或强度耗尽
            while (time > 0 && intensity >= 1) {
                long long distance;
                int id;
                if (!find_next(x, y, direction, distance, id) || distance > time) {
                    // 本次剩余时间内不再有碰撞，直线走完
                    if (direction == 0) x += time;
                    if (direction == 1) y += time;
                    if (direction == 2) x -= time;
                    if (direction == 3) y -= time;
                    time = 0;
                    break;
                }
                // 移动到碰撞点，消耗对应时间
                if (direction == 0) x += distance;
                if (direction == 1) y += distance;
                if (direction == 2) x -= distance;
                if (direction == 3) y -= distance;
                time -= distance;
                intensity *= segment[id].loss;      // 反射折损
                direction = reflected_direction(direction, segment[id].slope);
            }
            if (intensity < 1) cout << "0 0 0\n";   // 已耗散
            else cout << x << ' ' << y << ' ' << (long long)floor(intensity) << '\n';
        }
    }

    return 0;
}

复杂度

设所有线段内部整点总数为 $K$ 。插入和删除每个点都是有序集合操作，总代价为 $O(K\log K)$ ；单次查询每次碰撞在有序集合中找邻点，复杂度为 $O(H\log K)$ ，其中 $H$ 为碰撞次数；空间复杂度为 $O(K)$ 。

总结

将水平、竖直方向分开维护后，几何碰撞问题退化为一维有序集合中的邻点查询。只维护线段内部点自动排除了端点歧义，插入、删除和查询都统一处理。

题目来自第 26 次 CSP 认证 T4，评测使用自造高质量复刻数据。我们承认原始题面与大样例版权均归中国计算机学会（CCF）所有，因此题面与评测服务均免费对外开放。如果您认为我们侵犯了您的权益，可联系我们。

时间限制： 2.0 秒

空间限制： 512 MB

题目描述

光线追踪是计算机图形学领域的一个重要算法，其原理是追踪一束从光源发出的光，经过不同的反射面，最终到达摄像机处的过程。

在这道问题中，你需要实现一段程序来处理一个简易的光线追踪模型。

在平面中有一些反射面，为方便起见，我们设这些反射面都是线段，与坐标轴成 $45$ 度角摆放，且两个端点的坐标均为整数。为进一步简化问题，我们假设所有的反射表面都是镜面反射。任何一束光线照射到反射面上（为避免讨论，假设反射面不含端点）时，都会改变方向为相应的镜面反射方向。注意，反射面的两侧都可以反射光线。

平面中还有一些激光光源，每个光源位于一个坐标为整数的点上，会向某个水平或竖直的方向发射一定强度的激光。

所有的反射面都不是完美的，每个反射面有一个折损系数 $a$ ，当强度为 $I$ 的光线照射上去时，反射光线的强度会变成 $aI$ 。为了便于处理，你可以认为所有反射面的材质均不算太好也不算太糟，因此所有的 $a$ 均在 $0.2\sim 0.8$ 的范围内。

在一些超高速摄影问题中，有时甚至连光速都要考虑在内。在这个问题中，我们不妨假设激光在 $1$ 单位时间内恰好移动 $1$ 单位距离。然而，超高速摄影带来的往往是采样精度的损失，因此对于一束激光，最终采样到的光线强度都是向下取整后的数值。特别地，当一束激光的强度小于 $1$ 时，认为其已经完全耗散。

问题的最开始，平面上没有反射面也没有光源。接下来你需要处理若干个操作，每个操作形如：

$1~x_1~y_1~x_2~y_2~a$ ：在平面上插入一个分别以 $(x_1,y_1)$ 和 $(x_2,y_2)$ 为端点，反射系数为 $a$ 的反射面，保证反射面与坐标轴成 $45$ 度角摆放，且不与先前存在、且还没有被删除的反射面在非端点处相交；另外受到渲染效率的影响，问题中的所有反射面的总长度（可以理解为所有 $|x_1-x_2|$ 之和）不会太大；
$2~k$ ：删除第 $k$ 个操作插入的反射面，保证第 $k$ 个操作发生在当前操作之前，且为一个插入操作，且这个反射面还没有被删除；
$3~x~y~d~I~t$ ：在 $(x,y)$ 位置放置一个光源，发射光线方向为 $d$ ，强度为 $I$ ，求其所经 $t$ 时刻后光线到达的坐标以及采样得到的光线强度。其中 $d$ 的含义为： $d=0$ 表示沿 $x$ 坐标增加的方向， $d=1$ 表示沿 $y$ 坐标增加的方向， $d=2$ 表示沿 $x$ 坐标减小的方向， $d=3$ 表示沿 $y$ 坐标减小的方向。另外，保证光源不位于当前存在的某个反射面（不含端点）上。注意：如果 $t$ 时刻后光线刚好到达某个反射面，则其强度取反射后的强度。

输入格式

从标准输入读入数据。

第一行，一个正整数 $m$ 表示操作的总数量。

接下来 $m$ 行，每行描述一个操作，格式如题目描述。

其中，除了所有的 $a$ 和 $I$ 以外的输入均为绝对值不超过 $10^9$ 的整数，其中 $k$ 和 $t$ 为正整数； $a$ 和 $I$ 为小数点不超过 $6$ 位的正实数，其中 $a$ 在 $0.2\sim 0.8$ 之间， $I\le 10^9$ 。

输出格式

输出到标准输出。

对于每个查询操作输出一行 $3$ 个整数，形如 $x~y~I$ ，表示激光最终到达位置为 $(x,y)$ ，采样得到的光线强度为 $I$ 。特别地，如果采样得到的光线强度为 $0$ （即光线已耗散），你也就无需关心最终到达的坐标，而只需要输出 0 0 0 即可。

题目数据保证，你可以在计算时直接使用 $64$ 位浮点数的运算和取整操作，而无需担心可能的精度误差问题。

input1

1
2
3
4
5
6
7
87
1 0 4 2 2 0.4
1 2 2 0 0 0.45
3 -1 3 0 6 5
3 1 5 3 2.4 5
3 0 2 0 3 4
2 1
3 1 5 3 2.4 5

output1

子任务

测试点编号	$m\le$	特殊性质
$1\sim 3$	$1000$	所有光线的 $t\le 1000$ ，所有输入坐标的绝对值 $\le 1000$
$4\sim 7$	$1000$	无
$8\sim 10$	$10^5$	所有光线的 $t\le 10$
$11\sim 13$	$10^5$	所有 $1$ 操作在所有 $3$ 操作之前，且无 $2$ 操作
$14\sim 16$	$10^5$	所有光线的 $I=1$
$17\sim 20$	$10^5$	无

对于 $100\%$ 的数据，保证 $m\le 10^5$ ，所有反射面面 $|x_1-x_2|$ 之和不超过 $3\times 10^5$ 。

光线追踪

目录

形式化题目

思路

只维护线段内部整点

用有序集合找最近碰撞点

反射与折损

代码

复杂度

总结