C - 島巡りの冒険 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 366 点

問題文

高橋君は、N 個の島が点在する広大な海域にいます。島には 1 から N までの番号が付けられており、島 i は二次元平面上の座標 (X_i, Y_i) に位置しています。

高橋君は小型ボートを使って島から島へと移動します。高橋君は現在いる島から、ユークリッド距離が D 以下である別の島へ一度に移動することができます。ここで、島 i と島 j のユークリッド距離は \sqrt{(X_i - X_j)^2 + (Y_i - Y_j)^2} で定義されます。なお、一度訪れた島を再び訪れることも許されます。

高橋君は島 S からスタートし、島 T にたどり着きたいと考えています。島 S から島 T まで移動するために必要な最小の移動回数を求めてください。たどり着くことが不可能な場合は -1 を出力してください。

制約

  • 2 \leq N \leq 1500
  • 1 \leq D \leq 10^9
  • 1 \leq S \leq N
  • 1 \leq T \leq N
  • S \neq T
  • -10^9 \leq X_i \leq 10^9
  • -10^9 \leq Y_i \leq 10^9
  • i \neq j ならば (X_i, Y_i) \neq (X_j, Y_j)
  • 入力はすべて整数である

入力

N D S T
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N
  • 1 行目には、島の個数を表す N、一度に移動できる最大距離を表す D、出発する島の番号を表す S、目的の島の番号を表す T が、スペース区切りで与えられる。
  • 続く N 行では、各島の座標が与えられる。
  • このうち i 行目（1 \leq i \leq N）では、島 i の x 座標 X_i と y 座標 Y_i が、スペース区切りで与えられる。

出力

高橋君が島 S から島 T まで移動するために必要な最小の移動回数を 1 行で出力せよ。たどり着くことが不可能な場合は -1 を出力せよ。

入力例 1

5 3 1 5
0 0
2 1
-1 2
3 -1
4 3

出力例 1

2

入力例 2

4 2 1 4
0 0
1 1
2 0
100 100

出力例 2

-1

入力例 3

8 5 1 8
0 0
3 4
-2 3
1 -4
7 7
4 0
0 5
10 10

出力例 3

3

Score : 366 pts

Problem Statement

Takahashi is in a vast sea area dotted with N islands. The islands are numbered from 1 to N, and island i is located at coordinates (X_i, Y_i) on a two-dimensional plane.

Takahashi travels from island to island using a small boat. From his current island, he can move to another island in one step if the Euclidean distance between them is at most D. Here, the Euclidean distance between island i and island j is defined as \sqrt{(X_i - X_j)^2 + (Y_i - Y_j)^2}. Note that he is allowed to revisit islands he has already visited.

Takahashi starts at island S and wants to reach island T. Find the minimum number of moves required to travel from island S to island T. If it is impossible to reach island T, output -1.

Constraints

  • 2 \leq N \leq 1500
  • 1 \leq D \leq 10^9
  • 1 \leq S \leq N
  • 1 \leq T \leq N
  • S \neq T
  • -10^9 \leq X_i \leq 10^9
  • -10^9 \leq Y_i \leq 10^9
  • If i \neq j, then (X_i, Y_i) \neq (X_j, Y_j)
  • All input values are integers

Input

N D S T
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N
  • The first line contains N representing the number of islands, D representing the maximum distance that can be traveled in one move, S representing the number of the starting island, and T representing the number of the destination island, separated by spaces.
  • The following N lines give the coordinates of each island.
  • The i-th of these lines (1 \leq i \leq N) contains the x-coordinate X_i and y-coordinate Y_i of island i, separated by a space.

Output

Output in one line the minimum number of moves required for Takahashi to travel from island S to island T. If it is impossible to reach island T, output -1.

Sample Input 1

5 3 1 5
0 0
2 1
-1 2
3 -1
4 3

Sample Output 1

2

Sample Input 2

4 2 1 4
0 0
1 1
2 0
100 100

Sample Output 2

-1

Sample Input 3

8 5 1 8
0 0
3 4
-2 3
1 -4
7 7
4 0
0 5
10 10

Sample Output 3

3