P11757 [COTS 2014] 城市建设 / GRAD

你有一些城市，城市之间用双向道路连接，道路不会重叠（这里的重叠指的不是交叉，指的是两段道路的交也是一个长度不为 $0$ 的线段）。我们在二维坐标系上用点来表示这些城市。 道路网络一开始只有两座城市以及连接他们的双向道路组成，连接两座城市的道路是几何上连接这两个结点的直线，其长度就是这两个结点的欧几里得距离。 你需要模拟整个城市网络的建立过程，支持两种操作： - `d X Y A B`，在坐标 $(X,Y)$ 上新增一座城市（保证该点原来没有城市），并建立该城市到标号为 $A$ 和 $B$ 的双向道路。**而这两个现有城市 $A,B$ 本身必须已经由一条道路直接相连。** - `u A B`，查询 $A$ 到 $B$ 的最短路。 城市 $1,2$ 在输入中固定，此后每增加一个城市，就赋予下一个自然数作为其标号。

第一行两个整数，表示城市 $1$ 的坐标。 第二行两个整数，表示城市 $2$ 的坐标。 第三行一个整数 $N$，表示操作数量。 以下 $N$ 行，每行是两种操作的其中一个。

对于所有 `u` 操作，你需要输出一个实数，表两个城市之间的最短路。（误差在 $0.1$ 内是允许的）。

- Subtask $1$（$21$ pts）：满足 $N\le 10^3$。 - Subtask $2$（$24$ pts）：所有类型为 `u` 的命令中的城市 A 相同。 - Subtask $3$（$55$ pts）：$1\le N\le 10^5,0\le X_1,X_2,Y_1,Y_2\le 10^6$。