← 返回题目列表

AtCoder · awc0032_a

A. 烟花的亲密

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

分数: 266 分

问题陈述

夏日祭典的夜晚,高桥和青木正在不同的地点观看烟火。烟花表演期间, N 烟花燃放。

目前 i第 次烟火爆发,高桥在坐标处 (X_i, Y_i) 和青木在坐标 (P_i, Q_i) 在二维平面上。每个烟花的位置可能不同。

当烟花爆竹瞬间高桥和青木之间的欧几里德距离最大为 R,我们说他们“一起观看”。这里,两者之间的欧几里德距离为 i第一个烟花是 \sqrt{(X_i - P_i)^2 + (Y_i - Q_i)^2}.

其中 N 烟花,求两人一起观看的烟花数量。

约束

  • 1 \leq N \leq 10^5
  • 1 \leq R \leq 10^9
  • -10^9 \leq X_i, Y_i, P_i, Q_i \leq 10^9
  • 所有输入均为整数

输入

N R
X_1 Y_1 P_1 Q_1
X_2 Y_2 P_2 Q_2
\vdots
X_N Y_N P_N Q_N
  • 第一行包含烟花数量 N 和距离阈值 R 用于确定他们是否一起观看,并以空格分隔。
  • 的 (1 + i)第行 (1 \leq i \leq N) 包含高桥的坐标 (X_i, Y_i) 和青木的坐标 (P_i, Q_i) 此刻 i第 次烟花爆发,以空格分隔。

输出

将两人一起观看的烟花数量打印在一行中。


示例输入 1

3 5
0 0 3 4
0 0 6 0
1 1 1 1

示例输出 1

2

示例输入 2

2 1
0 0 10 10
5 5 0 0

示例输出 2

0

示例输入 3

6 10
0 0 3 4
0 0 8 6
0 0 11 0
5 5 5 5
-3 4 3 -4
100 100 0 0

示例输出 3

4

示例输入 4

10 1000000000
0 0 600000000 800000000
0 0 600000001 800000000
1000000000 1000000000 -1000000000 -1000000000
0 0 0 0
-500000000 -500000000 -500000000 -500000000
999999999 0 0 0
0 0 0 1000000000
100 200 300 400
-1000000000 0 1000000000 0
500000000 500000000 500000001 500000001

示例输出 4

7

示例输入 5

1 1
0 0 1 0

示例输出 5

1