E - Traveling to the Space Station Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 466 点

問題文

高橋君は宇宙飛行士として、宇宙空間での船外活動を行っています。現在、高橋君は母船から距離 W メートル離れた宇宙ステーションへ移動する必要があります。

宇宙空間には N 個のデブリ（宇宙ゴミ）が浮遊しており、高橋君はこれらのデブリを足場にしてステーションまで移動することができます。

母船の位置を y = 0 、宇宙ステーションの入口を y = W とする座標系を考えると、 i 番目のデブリは座標 (x_i, y_i) に位置しています。高橋君は最初、母船の座標 (0, 0) におり、宇宙ステーションの入口である座標 (0, W) に到達したいと考えています。

高橋君の宇宙服に搭載されたジェットパックは、現在地から距離 D 以下の場所にあるデブリ、または宇宙ステーションの入口へジャンプすることができます。ただし、母船から直接宇宙ステーションにジャンプすることはできません（安全上の理由から、必ず少なくとも 1 つのデブリを経由する必要があります）。

高橋君が宇宙ステーションに到達するために必要な最小ジャンプ回数を求めてください。ただし、どのようにデブリを選んでも宇宙ステーションに到達できない場合は -1 を出力してください。

なお、 2 点 (a, b) と (c, d) の距離は \sqrt{(a-c)^2 + (b-d)^2} で計算されます。

制約

  • 1 \leq N \leq 10^5
  • 2 \leq W \leq 10^9
  • 1 \leq D \leq 10^9
  • -10^9 \leq x_i \leq 10^9
  • 1 \leq y_i \leq W - 1
  • すべての入力値は整数

入力

N W D
x_1 y_1
x_2 y_2
:
x_N y_N
  • 1 行目には、デブリの個数 N 、母船から宇宙ステーションまでの距離 W 、ジャンプ可能な最大距離 D が、スペース区切りで与えられる。
  • 2 行目から N + 1 行目には、各デブリの座標が与えられる。
  • 1 + i 行目では、 i 番目のデブリの x 座標 x_i と y 座標 y_i が、スペース区切りで与えられる。

出力

高橋君が宇宙ステーションに到達するために必要な最小ジャンプ回数を 1 行で出力せよ。到達できない場合は -1 を出力せよ。

入力例 1

4 10 4
0 3
3 5
0 7
5 1

出力例 1

3

入力例 2

3 100 20
0 15
10 30
-10 40

出力例 2

-1

入力例 3

10 30 7
2 5
-3 6
1 11
-4 12
0 16
5 18
-2 21
3 24
0 26
10 15

出力例 3

6

入力例 4

20 100 15
0 12
5 24
-2 36
1 49
0 62
-4 74
3 86
0 95
14 5
-10 10
20 25
-15 30
8 40
-8 55
12 60
-12 70
15 80
-6 90
25 50
-20 85

出力例 4

8

入力例 5

1 1000000000 1000000000
0 500000000

出力例 5

2

Score : 466 pts

Problem Statement

Takahashi is an astronaut conducting extravehicular activity in outer space. Currently, he needs to travel to a space station that is W meters away from his mothership.

There are N pieces of debris (space junk) floating in space, and Takahashi can use these pieces of debris as footholds to move to the station.

Considering a coordinate system where the mothership is at y = 0 and the entrance of the space station is at y = W, the i-th piece of debris is located at coordinates (x_i, y_i). Takahashi is initially at the mothership at coordinates (0, 0) and wants to reach the entrance of the space station at coordinates (0, W).

The jetpack equipped on Takahashi's spacesuit allows him to jump to a piece of debris or the entrance of the space station that is within a distance of D from his current position. However, he cannot jump directly from the mothership to the space station (for safety reasons, he must visit at least 1 piece of debris).

Find the minimum number of jumps required for Takahashi to reach the space station. If it is impossible to reach the space station no matter which debris he chooses, output -1.

The distance between two points (a, b) and (c, d) is calculated as \sqrt{(a-c)^2 + (b-d)^2}.

Constraints

  • 1 \leq N \leq 10^5
  • 2 \leq W \leq 10^9
  • 1 \leq D \leq 10^9
  • -10^9 \leq x_i \leq 10^9
  • 1 \leq y_i \leq W - 1
  • All input values are integers.

Input

N W D
x_1 y_1
x_2 y_2
:
x_N y_N
  • The first line contains the number of pieces of debris N, the distance from the mothership to the space station W, and the maximum jump distance D, separated by spaces.
  • The 2-nd through (N + 1)-th lines provide the coordinates of each piece of debris.
  • The (1 + i)-th line contains the x-coordinate x_i and the y-coordinate y_i of the i-th piece of debris, separated by a space.

Output

Print the minimum number of jumps required for Takahashi to reach the space station in a single line. If it is impossible to reach, print -1.

Sample Input 1

4 10 4
0 3
3 5
0 7
5 1

Sample Output 1

3

Sample Input 2

3 100 20
0 15
10 30
-10 40

Sample Output 2

-1

Sample Input 3

10 30 7
2 5
-3 6
1 11
-4 12
0 16
5 18
-2 21
3 24
0 26
10 15

Sample Output 3

6

Sample Input 4

20 100 15
0 12
5 24
-2 36
1 49
0 62
-4 74
3 86
0 95
14 5
-10 10
20 25
-15 30
8 40
-8 55
12 60
-12 70
15 80
-6 90
25 50
-20 85

Sample Output 4

8

Sample Input 5

1 1000000000 1000000000
0 500000000

Sample Output 5

2