問題文
狐狸 Shieru 正在度假去一个小村庄。让她惊讶的是村子铭牌的性质。
在村里 有 N 房子。为了简单起见,我们假设村庄是一个二维平面,而房屋是这个平面上的点。 每栋房子都有一个铭牌,上面写着房子的姓氏。 Shieru在参观村庄时发现,这个村庄的铭牌有以下特点。
- 一些实数 R 存在。
- 如果两栋房子之间的距离是 如果 R 或更少,则两栋房屋具有相同的铭牌。
- 如果两栋房子之间的距离是 如果 3R 如果是这样,则两栋房子的铭牌不同。
- 任意两栋房子之间的距离是 是否小于或等于 R 它大于或等于 3R 。
这里,房屋之间的距离是使用平面上的欧几里德距离来测量的。
Shieru很好奇这个村庄里到底有多少种铭牌,但发现这个村庄出奇的大,于是他决定用计算器来寻找答案。
入力形式
输入按以下格式给出。
N\ R\\ x1\ y1\\ x2\ y2\\ ...\\ xN\ yN
N 是房屋数量。R 是与房屋安置限制相关的值。 (xi, yi) 是一座房子 表示 i 的坐标。
出力形式
找出村庄中存在的铭牌类型的数量。
制約
- 1 ≤ N ≤ 2 \times 105
- 1 ≤ R ≤ 103
- |xi|, |yi| ≤ 106
- N 是一个整数。R, xi, yi 是一个实数,表示为小数点后三位。
- 任何 对于 1 ≤ i < j ≤ N 当我们设置 dij = \sqrt{(xi - xj)2 + (yi - yj)2} 时,dij ≤ R 或 满足 3R ≤ dij 之一。
针对该问题的判断设置了一组15分的测试用例。除了上述约束之外,该组中包含的测试用例还满足以下约束。
- 答案是 10 或更少。
入出力例
入力例 1
5 3.000 1.000 0.000 0.000 0.000 -1.000 0.000 10.000 0.000 -10.000 0.000
出力例 1
3
1号、2号和3号房屋,4号和5号房屋有不同的铭牌。铭牌一共有三个。
入力例 2
12 1.234 0.500 0.000 -0.500 0.000 0.000 0.000 0.000 -0.500 55.500 55.000 -55.500 55.000 55.000 55.000 55.000 -55.500 99.500 99.000 -99.500 99.000 99.000 99.000 99.000 -99.500
出力例 2
7
入力例 3
5 99.999 0.000 0.000 49.999 0.001 0.000 0.000 -49.999 -0.001 0.000 0.000
出力例 3
1
作者:楠本满 测试员:奥巴马正太郎