← 返回题目列表

Codeforces · 350/C

C. 炸弹

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

你有一个机器人,它的任务是摧毁方形平面上的炸弹。具体来说,正方形平面包含n个炸弹,第i个炸弹位于坐标为(xi,yi)的点。我们知道没有两颗炸弹位于同一点,也没有炸弹位于坐标为 (0, 0) 的点。最初,机器人位于坐标 (0, 0) 的点。另外,我们将机器人的当前位置标记为 (x, y)。为了销毁所有炸弹,机器人可以执行三种类型的操作:

1. 操作的格式为“1 k dir”。为了执行该操作,机器人必须沿方向 dir k (k ≥ 1) 次移动。机器人只能移动 4 个方向:“R”、“L”、“U”、“D”。在一次移动过程中,机器人可以从当前点移动到以下点之一:(x + 1, y)、(x - 1, y)、(x, y + 1)、(x, y - 1)(对应方向)。如果路径上至少有一个点(除了目的地点)包含炸弹,则禁止从点 (x, y) 移动。
2. 操作的格式为“2”。要执行操作,机器人必须在点 (x, y) 拾取炸弹并将其放入特殊容器中。因此,机器人可以将炸弹从任何一点携带到任何其他点。如果(x, y)点没有炸弹,则无法执行该操作。如果机器人容器内已装有炸弹,则禁止拾取炸弹。
3. 操作的格式为“3”。要执行操作,机器人必须从容器中取出炸弹并将其摧毁。仅当机器人处于点(0, 0)时才允许执行此操作。容器内无炸弹时禁止进行操作。

帮助机器人找到他可以执行的最短操作序列,以摧毁坐标平面上的所有炸弹。

输入

第一行包含一个整数 n (1 ≤ n ≤ 105) — 坐标平面上的炸弹数量。接下来的 n 行每行包含两个整数。第 i 行包含数字 (xi, yi) (- 109 ≤ xi, yi ≤ 109) — 第 i 个炸弹的坐标。保证没有两个炸弹位于同一点,并且没有炸弹位于点 (0, 0)。

输出

在一行中打印一个整数 k — 销毁所有炸弹所需的最少操作数。接下来的几行打印这 k 个操作的描述。如果有多个序列,您可以打印其中任何一个。保证存在 k ≤ 106 的解。

示例

输入 #1

2
1 1
-1 -1

输出 #1

12
1 1 R
1 1 U
2
1 1 L
1 1 D
3
1 1 L
1 1 D
2
1 1 R
1 1 U
3

输入 #2

3
5 0
0 5
1 0

输出 #2

12
1 1 R
2
1 1 L
3
1 5 R
2
1 5 L
3
1 5 U
2
1 5 D
3