#P1885. [Coi2003]Locomotive

    ID: 907 传统题 1000ms 512MiB 尝试: 4 已通过: 4 难度: 8 上传者: 标签>CF2400提高+/省选-状态扩展图状态维度消除广度优先搜索状态去重点到线段距离平方距离比较

[Coi2003]Locomotive

题目描述

平面上有 NN 座城市。一些城市对之间有一段连接两座城市的直线铁路。Mirko 和 Slavko 各驾驶一台机车,从不同的城市出发。

两人可以沿铁路双向行驶,能独立选择速度,也可以停下等待。在到达城市时才可以改走另一段铁路。即使两段铁路在城市之外相交,也不能在交点换道。

Slavko 需要一直通过无线电接收 Mirko 的指示。整个移动过程中,两人之间的欧氏距离在任意时刻均不得超过 DD 千米。求 Slavko 可以到达的所有城市。对于不同的目标城市,可以分别选择不同的行驶方案。

输入格式

第一行包含两个整数 N,PN,P 和一个实数 DD,分别表示城市数、铁路数和通信距离。2≤N≤1002\le N\le100,1≤P≤30001\le P\le3000,1≤D≤100001\le D\le10000,DD 最多有两位小数。

接下来 NN 行,每行两个整数 X,YX,Y,表示相应城市的坐标(单位为千米,−5000≤X,Y≤5000-5000\le X,Y\le5000)。城市编号为 11 到 NN。

接下来 PP 行,每行两个城市编号 G1,G2G_1,G_2,表示它们之间有铁路。最后一行给出不同的两个城市编号 U,VU,V,分别是 Mirko 和 Slavko 的出发点,保证它们之间的欧氏距离不超过 DD。

输出格式

按从小到大的顺序输出 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

克罗地亚 2003 选拔赛第二试原题 VOKITOKI