← 返回题目列表

AtCoder · kupc2012_7

G. 村

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

問題文

狐狸 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

作者:楠本满
测试员:奥巴马正太郎