← 返回题目列表

Codeforces · 1949/A

A. 格罗夫

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

您想要在大小为 $$$n \times n$$$ 的方形草坪上种植树木,其角点具有笛卡尔坐标 $$$(0, 0)$$$、$$$(n, 0)$$$、$$$(0, n)$$$ 和 $$$(n, n)$$$。树木只能种植在具有整数坐标的位置。每棵树都会在以树种植位置为中心、半径为 $$$r$$$ 的圆盘内生长根;这些圆盘必须完全包含在草坪中(可能接触草坪的边界)并且只能在其边界上彼此相交。

找到最大化树数量的配置。

输入

第一行也是唯一一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 20$$$) 和一个实数 $$$r$$$ ($$$0 < r \leq n/2$$$) — 草坪边的长度,以及每棵树将生长根部的圆盘的半径。实数 $$$r$$$ 以十进制表示,小数点后最少为 $$$1$$$,最多为 $$$3$$$ 位。

输出

在第一行中,打印可以种植的最大树木数$$$m$$$。

在接下来的 $$$m$$$ 行中,打印最大化树数量的配置。具体来说,在第 $$$(i+1)$$$ 行中,打印两个整数 $$$x$$$ 和 $$$y$$$ — 应种植第 $$$i$$$ 树的位置的坐标。您可以按任何顺序打印树木。

如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

6 1.241

输出 #1

2
4 2
2 4

输入 #2

9 2.0

输出 #2

4
2 2
7 2
2 6
6 6

注意

对于第一个示例,示例输出如下图所示。请注意,这不是最大化树数量的唯一配置。

对于第二个示例,示例输出如下图所示。请注意,这不是最大化树数量的唯一配置。