#P11757. [COTS 2014] 城市建设 / GRAD
[COTS 2014] 城市建设 / GRAD
题目描述
你有一些城市,城市之间用单向道路连接,道路不会重叠。我们在二维坐标系上用点来表示这些城市。
道路网络一开始只有两座城市以及连接他们的双向道路组成,连接两座城市的道路的长度就是他们的欧几里得距离。
你需要模拟整个城市网络的建立过程,支持两种操作:
-
d X Y A B
,在坐标 上新增一座城市(保证该点原来没有城市),并建立该城市到标号为 和 的双向道路。 -
u A B
,查询 到 的最短路。
城市 在输入中固定,此后每增加一个城市,就赋予下一个自然数作为其标号。
输入格式
第一行两个整数,表示城市 的坐标。
第二行两个整数,表示城市 的坐标。
第三行一个整数 ,表示操作数量。
以下 行,每行是两种操作的其中一个。
输出格式
对于所有 u
操作,你需要输出一个实数,表两个城市之间的最短路。(误差在 内是允许的)。
6 4
10 4
9
d 6 7 2 1
u 1 2
u 3 2
d 10 2 1 2
u 3 4
d 12 7 2 4
u 5 3
u 4 5
u 1 5
4.000000
5.000000
7.000000
8.605551
5.385165
7.605551
1 1
3 8
10
d 8 2 1 2
u 2 1
d 2 9 1 3
u 1 4
d 4 7 3 4
u 4 3
d 6 1 5 4
u 6 5
d 0 0 4 6
u 7 3
7.280110
8.062258
9.219544
6.324555
18.439089
提示
-
Subtask ( pts):满足 。
-
Subtask ( pts):所有类型为
u
的命令中的城市 A 相同。 -
Subtask ( pts):。