← 返回题目列表

Codeforces · 2111/F

F. 谜题

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

你收到了一个拼图,该拼图的每一块都是一个边长为 1 的正方形。您可以将任何图片粘贴到该拼图上,然后将其剪切,并获得几乎普通的拼图游戏。

你的朋友是一位狂热的数学家,所以他建议你考虑以下问题。是否可以将拼图块排列成满足以下条件:

  • 碎片平行于坐标轴对齐;
  • 碎片彼此不重叠;
  • 所有碎片形成单个连接组件(即,存在从每个碎片到沿碎片的每个其他碎片的路径,其中每两个连续碎片共享一条边);
  • 该组件的周长与该组件的面积之比等于$$$\frac{p}{s}$$$;
  • 使用的件数不超过$$$50\,000$$$。

你能应付吗?

对于该图形,周长与面积的比率为 $$$\frac{11}{9}$$$

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的唯一行包含两个整数 $$$p$$$ 和 $$$s$$$ ($$$1 \le p, s \le 50$$$)。

输出

对于每个测试用例:

  • 如果无法按照上述方式排列棋子,则输出单个整数$$$-1$$$;
  • 否则,在第一行输出单个整数 $$$k$$$ ($$$1 \le k \le 50\,000$$$),然后在 $$$k$$$ 行中输出棋子的坐标:每行应包含两个整数 $$$x_{i}$$$ 和 $$$y_{i}$$$ ($$$-10^{9} \le x_{i}, y_{i} \le 10^{9}$$$)。如果有多个合适的棋子排列,则输出其中任何一个。

示例

输入
复制

2
1 1
31 4

输出
复制

20
3 7
3 8
6 4
6 5
3 5
4 4
4 5
4 3
3 4
5 3
5 4
5 7
3 6
4 6
5 5
5 6
4 7
4 8
6 6
6 7
-1

输入
复制

2
4 2
12 5

输出
复制

24
-7 2
-3 -3
-7 -5
-7 1
-3 2
-7 -2
-3 -5
-7 -6
-5 -6
-3 -4
-3 -6
-7 0
-6 -6
-7 -3
-5 2
-7 -1
-3 1
-4 -6
-3 0
-7 -4
-6 2
-4 2
-3 -1
-3 -2
5
0 0
0 1
1 0
-1 0
0 -1

注意

在第一个测试的第一个测试用例中,图可能是这样的:

在第二次测试中,数字如下所示:

请注意,内部周长也被考虑在内!