P13913 [CSPro 26] 光线追踪

洛谷的测试数据仅供民间交流使用，非官方测试数据。官方评测链接：。

光线追踪是计算机图形学领域的一个重要算法，其原理是追踪一束从光源发出的光，经过不同的反射面，最终到达摄像机处的过程。 在这道问题中，你需要实现一段程序来处理一个简易的光线追踪模型。 在平面中有一些反射面，为方便起见，我们设这些反射面都是线段，与坐标轴成 45 度角摆放，且两个端点的坐标均为整数。为进一步简化问题，我们假设所有的反射表面都是镜面反射。任何一束光线照射到反射面上（为避免讨论，假设反射面不含端点）时，都会改变方向为相应的镜面反射方向。注意，反射面的两侧都可以反射光线。 平面中还有一些激光光源，每个光源位于一个坐标为整数的点上，会向某个水平或竖直的方向发射一定强度的激光。 所有的反射面都不是完美的，每个反射面有一个折损系数 $a$，当强度为 $I$ 的光线照射上去时，反射光线的强度会变成 $aI$。为了便于处理，你可以认为所有反射面的材质均不算太好也不算太糟，因此所有的 $a$ 均在 $0.2 \sim 0.8$ 的范围内。 在一些超高速摄影问题中，有时甚至连光速都要考虑在内。在这个问题中，我们不妨假设激光在 1 单位时间内恰好移动 1 单位距离。然而，超高速摄影带来的往往是采样精度的损失，因此对于一束激光，最终采样到的光线强度都是向下取整后的数值。特别地，当一束激光的强度小于 1 时，认为其已经完全耗散。 问题的最开始，平面上没有反射面也没有光源。接下来你需要处理若干个操作，每个操作形如： `1 x1 y1 x2 y2 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$ 时刻后光线刚好到达某个反射面，则其强度取反射后的强度。

从标准输入读入数据。 第 1 行，一个正整数 $m$ 表示操作的总数量。 接下来 $m$ 行，每行描述一个操作，格式如题目描述。 其中，除了所有的 $a$ 和 $I$ 以外的输入均为绝对值不超过 $10^9$ 的整数，其中 $k$ 和 $t$ 为正整数；$a$ 和 $I$ 均为小数点后不超过 6 位的正实数，其中 $a$ 在 $0.2 \sim 0.8$ 之间，$I \leq 10^9$。

输出到标准输出。 对于每个查询操作输出一行，$3$ 个整数，形如 $x\ y\ I$ 表示激光最终到达的位置为 $(x, y)$，采样得到的光线强度为 $I$。特别地，如果采样到的光线强度为 $0$（即光线已耗散），你也无需关心最终到达的坐标，而只需要输出 $0\ 0\ 0$ 即可。 题目数据保证，你可以在计算时直接使用 $64$ 位浮点数的运算和取整操作，而无需担心可能的精度误差问题。

### 数据范围 ::cute-table{tuack} | 测试点编号 | $m \leq$ | 特殊性质 | | :-: | :-: | :-: | | $1 \sim 3$ | $1000$ | 所有光线的 $t \leq 1000$，所有输入坐标的绝对值 $\leq 1000$ | | $4 \sim 7$ | ^ | 无 | | $8 \sim 10$ | $10^5$ | 所有光线的 $t \leq 10$ | | $11 \sim 13$ | ^ | 所有 1 操作在所有 3 操作之前，且无 2 操作 | | $14 \sim 16$ | ^ | 所有光线的 $I = 1$ | | $17 \sim 20$ | ^ | 无 | 对于 $100\%$ 的数据，保证 $m \leq 10^5$，所有反射面的 $|x_1 - x_2|$ 之和不超过 $3 \times 10^5$。