/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 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
- 1 行目には、花火の数 N と、一緒に観たと判定する距離の閾値 R が、スペース区切りで与えられる。
- 1 + i 行目 (1 \leq i \leq N) には、i 発目の花火が開いた瞬間の高橋君の座標 (X_i, Y_i) と青木君の座標 (P_i, Q_i) が、スペース区切りで与えられる。
出力
二人が一緒に観た花火の数を 1 行で出力してください。
入力例 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
Score : 266 pts
Problem Statement
On the night of a summer festival, Takahashi and Aoki are watching fireworks from different locations. During the fireworks show, N fireworks are launched.
At the moment the i-th firework bursts, Takahashi is at coordinates (X_i, Y_i) and Aoki is at coordinates (P_i, Q_i) on a two-dimensional plane. Their positions may differ for each firework.
When the Euclidean distance between Takahashi and Aoki at the moment a firework bursts is at most R, we say they "watched it together." Here, the Euclidean distance between the two for the i-th firework is \sqrt{(X_i - P_i)^2 + (Y_i - Q_i)^2}.
Among the N fireworks, find the number of fireworks that the two watched together.
Constraints
- 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
- All inputs are integers
Input
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
- The first line contains the number of fireworks N and the distance threshold R for determining whether they watched together, separated by a space.
- The (1 + i)-th line (1 \leq i \leq N) contains Takahashi's coordinates (X_i, Y_i) and Aoki's coordinates (P_i, Q_i) at the moment the i-th firework bursts, separated by spaces.
Output
Print the number of fireworks the two watched together in one line.
Sample Input 1
3 5 0 0 3 4 0 0 6 0 1 1 1 1
Sample Output 1
2
Sample Input 2
2 1 0 0 10 10 5 5 0 0
Sample Output 2
0
Sample Input 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
Sample Output 3
4
Sample Input 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
Sample Output 4
7
Sample Input 5
1 1 0 0 1 0
Sample Output 5
1