← 返回题目列表

Codeforces · 392/A

A. 被阻止的点

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

假设您有一个带有笛卡尔坐标系的无限二维平面。有的积分点被屏蔽,有的则没有。平面上的两个积分点 A 和 B 是 4 连通的当且仅当:

- A和B之间的欧氏距离为1个单位,并且A和B都没有被阻挡;
- 或者存在某个积分点 C,使得 A 与 C 4-连通,C 与 B 4-连通。

假设平面不包含被阻挡的点。考虑平面上与原点的欧氏距离不大于n的所有积分点,我们将这些点命名为特殊的。 Chubby Yang想要得到以下性质:没有特殊点与某个非特殊点是4连通的。为了获得财产,她可以选择飞机上的一些积分点并将它们封锁。她需要选择的最少点数是多少?

输入

第一行包含一个整数 n (0 ≤ n ≤ 4·107)。

输出

打印一个整数——应该被阻止的最小点数。

示例

输入 #1

1

输出 #1

4

输入 #2

2

输出 #2

8

输入 #3

3

输出 #3

16