← 返回题目列表

Codeforces · 1184/C2

C2. 海蒂和图灵测试(中)

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

网络人解决第一个测试的速度比戴立克人快得多。对我们来说幸运的是,戴立克人很生气(令人震惊!),他们摧毁了一些网络人。

战斗停止后,海蒂又给了他们一个任务来消磨时间。

平面上有 $$$n$$$ 个点。给定半径 $$$r$$$,找到半径为 $$$r$$$ 的 $$$L^1$$$ 球可以覆盖的最大点数。

2D 平面中半径为 $$$r$$$ 且中心为 $$$(x_0, y_0)$$$ 的 $$$L^1$$$ 球被定义为点集 $$$(x, y)$$$,使得 $$$(x_0, y_0)$$$ 和 $$$(x, y)$$$ 之间的曼哈顿距离最多为$$$r$$$。

$$$(x_0, y_0)$$$ 和 $$$(x, y)$$$ 之间的曼哈顿距离定义为 $$$|x - x_0| + |y - y_0|$$$。

输入

第一行包含两个整数 $$$n, r$$$ ($$$1 \le n \le 300\,000, 1 \le r \le 10^6$$$),分别是点数和球的半径。

接下来的 $$$n$$$ 行包含整数 $$$x_i, y_i$$$ ($$$-10^6 \leq x_i, y_i \leq 10^6$$$),描述第 $$$i$$$ 个点的坐标。

保证所有点都是不同的。

输出

打印一个整数——半径为 $$$r$$$ 的 $$$L^1$$$ 球可以覆盖的最大点数。

示例

输入 #1

5 1
1 1
1 -1
-1 1
-1 -1
2 0

输出 #1

3

输入 #2

5 2
1 1
1 -1
-1 1
-1 -1
2 0

输出 #2

5

注意

在第一个示例中,以 $$$(1, 0)$$$ 为中心的球覆盖了点 $$$(1, 1)$$$、$$$(1, -1)$$$、$$$(2, 0)$$$。

在第二个示例中,以 $$$(0, 0)$$$ 为中心的球覆盖了所有点。

请注意,$$$x_0$$$ 和 $$$y_0$$$ 不必是整数。