D - 机械臂

分数 : $600$ 分

问题描述

Snuke希望在他的工厂引入一种机械臂，具有以下特点:

• 机械臂由$m$个节段和$m+1$个关节组成。节段编号为$1$, $2$, ..., $m$，关节编号为$0$, $1$, ..., $m$。节段$i$连接关节$i-1$和关节$i$。节段$i$的长度为$d_i$。
• 每个节段都可以单独指定模式。共有四种模式：L，R，D和U。节段的模式决定了节段的方向。如果将工厂视为笛卡尔坐标平面，则关节$i$的位置将按照以下规则确定（我们用$(x_i, y_i)$表示其坐标）：
  • $(x_0, y_0) = (0, 0)$。
  • 如果节段$i$的模式为L，则$(x_{i}, y_{i}) = (x_{i-1} - d_{i}, y_{i-1})$。
  • 如果节段$i$的模式为R，则$(x_{i}, y_{i}) = (x_{i-1} + d_{i}, y_{i-1})$。
  • 如果节段$i$的模式为D，则$(x_{i}, y_{i}) = (x_{i-1}, y_{i-1} - d_{i})$。
  • 如果节段$i$的模式为U，则$(x_{i}, y_{i}) = (x_{i-1}, y_{i-1} + d_{i})$。

Snuke希望通过适当指定节段的模式，使得关节$m$的位置能够与所有$N$个点$(X_1, Y_1), (X_2, Y_2), ..., (X_N, Y_N)$匹配。 这可能吗？ 如果可能，请找到这样的机械臂以及将关节$m$移动到每个点$(X_j, Y_j)$的方式。

约束

• 所有输入值均为整数。
• $1 \leq N \leq 1000$
• $-10^9 \leq X_i \leq 10^9$
• $-10^9 \leq Y_i \leq 10^9$

部分分

• 对于价值300分的测试用例，保证$-10 \leq X_i \leq 10$和$-10 \leq Y_i \leq 10$。

---

输入

从标准输入中以以下格式给出：

$N$

$X_1$ $Y_1$

$X_2$ $Y_2$

$:$

$X_N$ $Y_N$

输出

如果条件可以满足，请按以下格式输出。如果条件无法满足，则输出-1。

``` $m$ $d_1$ $d_2$ $...$ $d_m$ $w_1$ $w_2$ $:$ $w_N$ ```

$m$和$d_i$是机械臂的配置。详细解释请参阅问题描述。 此处，要求$1 \leq m \leq 40$，$1 \leq d_i \leq 10^{12}$。而且$m$和$d_i$都必须是整数。

$w_j$是一个长度为$m$的字符串，表示将机械臂的第$m$个关节移动到点$(X_j, Y_j)$的方法。 $w_j$的第$i$个字符应为L，R，D或U中的一个，表示第$i$个节段的模式。

---

3
-1 0
0 3
2 -1

2
1 2
RL
UU
DR

根据给定的方式，将机械臂的第$m$个关节移动到每个点$(X_j, Y_j)$时，关节的位置如下：

• 对于$(X_1, Y_1) = (-1, 0)$，关节$0$的位置为$(x_0, y_0) = (0, 0)$。由于节段$1$的模式为R，关节$1$的位置为$(x_1, y_1) = (1, 0)$。然后，节段$2$的模式为L，关节$2$的位置为$(x_2, y_2) = (-1, 0)$。
• 对于$(X_2, Y_2) = (0, 3)$，有$(x_0, y_0) = (0, 0), (x_1, y_1) = (0, 1), (x_2, y_2) = (0, 3)$。
• 对于$(X_3, Y_3) = (2, -1)$，有$(x_0, y_0) = (0, 0), (x_1, y_1) = (0, -1), (x_2, y_2) = (2, -1)$。

---

5
0 0
1 0
2 0
3 0
4 0

-1

---

2
1 1
1 1

2
1 1
RU
UR

$(X_j, Y_j)$之间可能存在重复点。

---

3
-7 -3
7 3
-3 -7

5
3 1 4 1 5
LRDUL
RDULR
DULRD