A - Wi-Fi Coverage Range Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 266 点

問題文

高橋君は、大学のキャンパス内に設置された Wi-Fi ルーターの電波がどの建物まで届くかを調査しています。

キャンパスには N 棟の建物があり、i 番目の建物 (1 \leq i \leq N) は座標 (X_i, Y_i) に位置しています。同じ座標に複数の建物が存在する場合もありますが、それぞれ別の建物として数えます。

Wi-Fi ルーターは座標 (0, 0) にある管理棟の屋上に設置されています。管理棟は調査対象の N 棟には含まれません。

Wi-Fi の電波は、ルーターからのユークリッド距離が D 以下の建物に届きます。すなわち、i 番目の建物に Wi-Fi の電波が届くのは、

\sqrt{X_i^2 + Y_i^2} \leq D

を満たすとき、つまり

X_i^2 + Y_i^2 \leq D^2

を満たすときです。

Wi-Fi の電波が届かない建物の数を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq D \leq 10^6
  • -10^6 \leq X_i \leq 10^6
  • -10^6 \leq Y_i \leq 10^6
  • 入力はすべて整数

入力

N D
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N
  • 1 行目には、建物の数を表す整数 N と、電波が届く最大距離を表す整数 D が、スペース区切りで与えられる。
  • 2 行目から N+1 行目では、各建物の座標が与えられる。
  • i+1 行目には、i 番目の建物の x 座標 X_i と y 座標 Y_i が、スペース区切りで与えられる。

出力

Wi-Fi の電波が届かない建物の数を 1 行で出力してください。

入力例 1

5 10
3 4
8 6
12 5
-5 0
7 -7

出力例 1

1

入力例 2

8 100
50 50
-30 40
80 60
0 100
100 1
-70 -70
25 -25
0 -150

出力例 2

2

入力例 3

12 1000
100 200
-500 500
700 700
0 1000
1000 0
-800 -600
300 -400
999 1
-1 999
600 800
-707 -708
450 -900

出力例 3

2

Score : 266 pts

Problem Statement

Takahashi is investigating which buildings on a university campus can be reached by the signal from a Wi-Fi router installed on campus.

There are N buildings on the campus, and the i-th building (1 \leq i \leq N) is located at coordinates (X_i, Y_i). Multiple buildings may exist at the same coordinates, but each is counted as a separate building.

The Wi-Fi router is installed on the rooftop of the administration building located at coordinates (0, 0). The administration building is not included in the N buildings being investigated.

The Wi-Fi signal reaches buildings whose Euclidean distance from the router is at most D. That is, the Wi-Fi signal reaches the i-th building when

\sqrt{X_i^2 + Y_i^2} \leq D

is satisfied, or equivalently when

X_i^2 + Y_i^2 \leq D^2

is satisfied.

Find the number of buildings that the Wi-Fi signal does not reach.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq D \leq 10^6
  • -10^6 \leq X_i \leq 10^6
  • -10^6 \leq Y_i \leq 10^6
  • All inputs are integers

Input

N D
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N
  • The first line contains an integer N representing the number of buildings and an integer D representing the maximum distance the signal can reach, separated by a space.
  • From the 2nd line to the (N+1)-th line, the coordinates of each building are given.
  • The (i+1)-th line contains the x-coordinate X_i and y-coordinate Y_i of the i-th building, separated by a space.

Output

Output the number of buildings that the Wi-Fi signal does not reach, on a single line.

Sample Input 1

5 10
3 4
8 6
12 5
-5 0
7 -7

Sample Output 1

1

Sample Input 2

8 100
50 50
-30 40
80 60
0 100
100 1
-70 -70
25 -25
0 -150

Sample Output 2

2

Sample Input 3

12 1000
100 200
-500 500
700 700
0 1000
1000 0
-800 -600
300 -400
999 1
-1 999
600 800
-707 -708
450 -900

Sample Output 3

2