← 返回题目列表

Codeforces · 618/E

E. 机器人手臂

中文机器翻译题面 查看原题

罗杰是一个机器人。他有一条手臂,由一系列相互连接的 n 段组成。第 i 段的端点最初位于点 (i - 1, 0) 和 (i, 0)。对于所有线段,(i - 1, 0) 处的端点为红色,(i, 0) 处的端点为蓝色。因此,对于所有有效的 i,第 i 段的蓝色端点与第 (i + 1) 段的红色端点相接触。

罗杰可以通过两种不同的方式移动他的手臂:

1.他可以选择一些段和一些值。这表示为选择段号 i 并选择一些正 l。这种变化发生如下:段号 i 的红色端点和从 1 到 i - 1 的段都固定在适当的位置。想象一条从红色端点到蓝色端点的射线。蓝色端点和线段 i + 1 到 n 沿该射线的方向平移 l 个单位。 在此图中,标记为 A 的红点和 A 之前的段保持原位,而标记为 B 的蓝点和 B 之后的段被平移。
2. 他可以选择一段并旋转它。这表示为选择段号 i 和角度 a。第 i 段的红色端点将保持固定。该线段和线段 i + 1 到 n 的蓝色端点将围绕红色端点顺时针旋转 a 度角。 在此图中,标记为 A 的红点和 A 之前的线段保持原位,而标记为 B 的蓝点和 B 之后的线段围绕 A 点旋转。

Roger 将移动他的手臂 m 次。这些转换有点复杂,罗杰很容易忘记最后一段的蓝色端点在哪里。在应用每个操作后,帮助他计算最后一段蓝色端点的坐标。请注意,这些操作是累积的,罗杰的手臂在移动过程中可能会任意相交。

输入

输入的第一行将包含两个整数 n 和 m (1 ≤ n, m ≤ 300 000) - 段数和要执行的操作数。

接下来的 m 行中的每一行都包含三个整数 xi、yi 和 zi 来描述一次移动。如果 xi = 1,则该行描述类型 1 的移动,其中 yi 表示段号,zi 表示长度的增加。如果 xi = 2,则描述类型 2 的移动,其中 yi 表示段号,zi 表示角度(以度为单位)。 (1≤xi≤2、1≤yi≤n、1≤zi≤359)

输出

打印 m 行。第 i 行应包含两个实数值,表示应用操作 1, ..., i 后最后一段的蓝色端点的坐标。如果您的答案的绝对或相对误差不超过 10 - 4,则视为正确。

也就是说,假设您对特定坐标值的答案是 a,陪审团的答案是 b。如果所有坐标的 $$\frac{|a-b|}{\max(1,b)} \leq 10^{-4}$$ ,检查程序将认为您的答案正确。

示例

输入 #1

5 4
1 1 3
2 3 90
2 5 48
1 4 1

输出 #1

8.0000000000 0.0000000000
5.0000000000 -3.0000000000
4.2568551745 -2.6691306064
4.2568551745 -3.6691306064

注意

下图显示了每次操作后手臂的状态。应用每次操作后都会打印 F 点的坐标。为简单起见,我们仅显示线段的蓝色端点(第一个线段的红色端点除外)。例如,标记为 B 的点是线段 1 的蓝色端点,也是线段 2 的红色端点。

初始状态: