← 返回题目列表

Codeforces · 460/E

E. 罗兰和罗斯

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

罗兰喜欢养花。他最近在笛卡尔坐标系的 (0, 0) 点种植了一朵美丽的玫瑰。这朵玫瑰花如此美丽,罗兰担心邪恶势力会试图偷走它。

为了保护玫瑰,罗兰想要建造n座瞭望塔。我们假设塔是平面上距离玫瑰最多 r 的点。此外,罗兰还假设塔楼应该建在坐标为整数的点上,并且所有对塔楼之间的距离平方和必须尽可能大。请注意,罗兰可能会在同一点建造多个塔,也可能会在点 (0, 0) 建造其中一些塔。

帮助罗兰在整数点建造塔,使所有塔之间的距离平方和尽可能最大。请注意,此问题中的距离定义为点之间的欧几里得距离。

输入

第一行包含两个整数 n 和 r (2 ≤ n ≤ 8; 1 ≤ r ≤ 30)。

输出

在第一行中打印一个整数 - 最大可能的平方距离之和。在接下来的 n 行的第 i 行中,打印两个整数 xi、yi — 第 i 个塔的坐标。每个塔必须位于半径为 r 的圆的内部或边界上。请注意,可能有多个塔位于平面的同一点,也可能有一些塔位于点 (0, 0)。

如果有多个有效的最优安排,请选择其中任何一个。

示例

输入 #1

4 1

输出 #1

16
0 1
0 1
0 -1
0 -1

输入 #2

3 6

输出 #2

312
0 6
5 -3
-5 -3