← 返回题目列表

Codeforces · 1584/G

G. 符合条件的航段

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

给你平面上 $$$n$$$ 不同的点 $$$p_1, p_2, \ldots, p_n$$$ 和一个正整数 $$$R$$$。

找到索引对 $$$(i, j)$$$ 的数量,使得 $$$1 \le i < j \le n$$$,并且对于每个可能的 $$$k$$$ ($$$1 \le k \le n$$$),从点 $$$p_k$$$ 到点 $$$p_i$$$ 和 $$$p_j$$$ 之间的线段的距离最多为$$$R$$$。

输入

第一行包含两个整数 $$$n$$$、$$$R$$$ ($$$1 \le n \le 3000$$$, $$$1 \le R \le 10^5$$$) — 点的数量以及点和线段之间的最大距离。

接下来的 $$$n$$$ 行包含两个整数 $$$x_i$$$、$$$y_i$$$ ($$$-10^5 \le x_i, y_i \le 10^5$$$),定义第 $$$i$$$ 个点 $$$p_i=(x_i, y_i)$$$。所有点都是不同的。

如果参数$$$R$$$改变最多$$$10^{-2}$$$,则保证答案不会改变。

输出

打印合适的对 $$$(i, j)$$$ 的数量。

示例

输入 #1

4 2
0 1
0 -1
3 0
-3 0

输出 #1

1

输入 #2

3 3
1 -1
-1 -1
0 1

输出 #2

3

注意

在第一个示例中,唯一的一对点 $$$(-3, 0)$$$, $$$(3, 0)$$$ 是合适的。从点 $$$(0, 1)$$$ 和 $$$(0, -1)$$$ 到这些点之间的线段的距离等于 $$$1$$$,小于 $$$R=2$$$。

在第二个示例中,所有可能的点对都符合条件。