#P11757. [COTS 2014] 城市建设 / GRAD

    ID: 13136 远端评测题 1500ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2014Special JudgeCOCI(克罗地亚)

[COTS 2014] 城市建设 / GRAD

题目描述

你有一些城市,城市之间用单向道路连接,道路不会重叠。我们在二维坐标系上用点来表示这些城市。

道路网络一开始只有两座城市以及连接他们的双向道路组成,连接两座城市的道路的长度就是他们的欧几里得距离。

你需要模拟整个城市网络的建立过程,支持两种操作:

  • d X Y A B,在坐标 (X,Y)(X,Y) 上新增一座城市(保证该点原来没有城市),并建立该城市到标号为 AABB 的双向道路。

  • u A B,查询 AABB 的最短路。

城市 1,21,2 在输入中固定,此后每增加一个城市,就赋予下一个自然数作为其标号。

输入格式

第一行两个整数,表示城市 11 的坐标。

第二行两个整数,表示城市 22 的坐标。

第三行一个整数 NN,表示操作数量。

以下 NN 行,每行是两种操作的其中一个。

输出格式

对于所有 u 操作,你需要输出一个实数,表两个城市之间的最短路。(误差在 0.10.1 内是允许的)。

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 112121 pts):满足 N103N\le 10^3

  • Subtask 222424 pts):所有类型为 u 的命令中的城市 A 相同。

  • Subtask 335555 pts):1N105,0X1,X2,Y1,Y21061\le N\le 10^5,0\le X_1,X_2,Y_1,Y_2\le 10^6