← 返回题目列表

Codeforces · 1276/E

E. 四块石头

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

在整数坐标 $$$a_1, a_2, a_3, a_4$$$ 的无限直线上有四个石头。目标是让棋子位于坐标 $$$b_1、b_2、b_3、b_4$$$ 中。棋子的顺序并不重要,也就是说,任何位置 $$$a_i$$$ 的棋子都可以到达任何位置 $$$b_j$$$,前提是每个位置都有所需的棋子数量(也就是说,如果坐标 $$$x$$$ 在数字 $$$b_1, \ldots, b_4$$$ 中出现 $$$k$$$ 次,则在 $$$k$$$ 处应该正好有 $$$k$$$ 棋子$$$x$$$ 最后)。

我们可以通过以下操作移动棋子:在$$$x$$$和$$$y$$$不同位置选择两颗棋子,每个棋子至少各有一颗棋子,并从$$$x$$$移动一颗棋子到$$$2y - x$$$。换句话说,该操作将棋子移动到相对于其他棋子对称的位置。在任何时刻,同一位置都允许有任意数量的棋子。

找到实现目标的任何操作序列,或者确定它是不可能的。该序列不必是最短的,但它最多可以包含 $$$1000$$$ 操作。

输入

第一行包含四个整数 $$$a_1, \ldots, a_4$$$ ($$$-10^9 \leq a_i \leq 10^9$$$) - 石头的初始坐标。可能有多个石子共享相同的坐标。

第二行包含四个整数 $$$b_1, \ldots, b_4$$$ ($$$-10^9 \leq b_i \leq 10^9$$$) - 棋子的目标坐标。可能有多个目标共享相同的坐标。

输出

如果没有可以实现目标的操作序列,则打印单个整数 $$$-1$$$。否则,在第一行打印一个整数 $$$k$$$ ($$$0 \leq k \leq 1000$$$) — 序列中的操作数。在接下来的 $$$k$$$ 行中,描述操作。这些行中的第 $$$i$$$ 应包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$x_i \neq y_i$$$) — 第 $$$i$$$ 操作的移动棋子和对称棋子中心的坐标。

对于每个操作 $$$i$$$,坐标 $$$x_i$$$ 和 $$$y_i$$$ 中每个都至少有一个石头,并且得到的坐标 $$$2y_i - x_i$$$ 的绝对值不得超过 $$$10^{18}$$$。

如果有多个合适的序列,则打印其中任何一个。保证如果存在合适的操作序列,则也存在满足所有附加要求的合适序列。

示例

输入 #1

0 1 2 3
3 5 6 8

输出 #1

3
1 3
2 5
0 3

输入 #2

0 0 0 0
1 1 1 1

输出 #2

-1

输入 #3

0 0 0 1
0 1 0 1

输出 #3

-1