分数: 366 分
问题陈述
高桥位于一片广阔的海域,星罗棋布。 N 岛屿。岛屿编号为 1 to N和岛屿 i 位于坐标处 (X_i, Y_i) 在二维平面上。
高桥乘坐小船从一个岛到另一个岛。从当前的岛屿,他可以一步移动到另一个岛屿,如果它们之间的欧氏距离最多为 D。这里,岛屿之间的欧几里得距离 i 和岛 j 定义为 \sqrt{(X_i - X_j)^2 + (Y_i - Y_j)^2}。请注意,他可以重新访问他已经访问过的岛屿。
高桥从岛上出发 S 想要到达岛屿 T。求从岛屿出发所需的最少移动次数 S 去岛 T。如果无法到达岛屿 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
- If 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
- 第一行包含 N 代表岛屿数量, D 代表一次移动可以移动的最大距离, S 代表起始岛屿的编号,以及 T 代表目的岛屿编号,以空格分隔。
- 以下 N 行给出了每个岛屿的坐标。
- 的 i这些行中的第 (1 \leq i \leq N) 包含 x- 坐标 X_i 和 y- 坐标 Y_i 岛屿的 i,用空格分隔。
输出
一行输出高桥离开岛屿所需的最少移动次数 S 去岛 T。如果无法到达岛屿 T,输出 -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