#P1885. [Coi2003]Locomotive
[Coi2003]Locomotive
题目描述
平面上有 座城市。一些城市对之间有一段连接两座城市的直线铁路。Mirko 和 Slavko 各驾驶一台机车,从不同的城市出发。
两人可以沿铁路双向行驶,能独立选择速度,也可以停下等待。在到达城市时才可以改走另一段铁路。即使两段铁路在城市之外相交,也不能在交点换道。
Slavko 需要一直通过无线电接收 Mirko 的指示。整个移动过程中,两人之间的欧氏距离在任意时刻均不得超过 千米。求 Slavko 可以到达的所有城市。对于不同的目标城市,可以分别选择不同的行驶方案。
输入格式
第一行包含两个整数 和一个实数 ,分别表示城市数、铁路数和通信距离。,,, 最多有两位小数。
接下来 行,每行两个整数 ,表示相应城市的坐标(单位为千米,)。城市编号为 到 。
接下来 行,每行两个城市编号 ,表示它们之间有铁路。最后一行给出不同的两个城市编号 ,分别是 Mirko 和 Slavko 的出发点,保证它们之间的欧氏距离不超过 。
输出格式
按从小到大的顺序输出 Slavko 能到达的每座城市的编号,每个编号占一行。出发城市也计入。
样例
5 4 1.5
0 1
0 0
4 1
4 0
2 2
1 3
1 5
3 5
2 4
2 1
1
3