[AdditionalFile6989.zip](file://AdditionalFile6989.zip?type=additional_file)

#6989. 「ICPC World Finals 2025」熔岩护城河

标签: 传统 | 时间限制: 4000 ms | 内存限制: 1024 MiB |

题目描述

这些烦人的正义大军又来打扰哥布林们宁静祥和的土地了。修建一堵巨大的墙效果不太好，所以哥布林们决定求助于久经考验的经典防御手段：一条充满熔岩的护城河。他们想挖这条护城河作为北部哥布林领地和南部行善者领地之间的边界，贯穿整个边境地带的东西两端。

这给他们带来了挑战。边境地带多山，甚至可以说是山区，而熔岩护城河必须全部处于同一水平面上——否则，较高处的熔岩会流到较低处并流出护城河。因此，哥布林们必须选择一条海拔完全相同的路径，并且要连接边境地带的西部边界和东部边界。出于显而易见的经济原因，他们希望这条路径尽可能短。

这就是你的用武之地了。你将得到一张边境地带的海拔地图，你的任务是确定这条护城河可以有多短。

地图的形式是一个尺寸为 $w \times \ell$ 的完全三角化的矩形，所有三角形的面积都为正。任何三角形的顶点都不会位于另一个三角形边的内部。地图的西南角坐标为 $(0,0)$，$x$ 轴向东，$y$ 轴向北。此外，西部边界（连接 $(0,0)$ 和 $(0, \ell)$ 的线段，包括端点）是一条单独的边。同样，东部边界（在点 $(w, 0)$ 和 $(w, \ell)$ 之间）也是一条单独的边。

当然，这张地图只是实际 3D 地形的 2D 投影：每个点 $(x, y)$ 还有一个海拔高度 $z$。三角剖分中顶点的海拔高度由地图直接指定，并且所有给定的海拔高度都是唯一的。所有其他点的海拔高度可以通过在相关三角形上进行线性插值来计算。换句话说，地形的形状就像是由共享边连接在一起的一系列三角形面片。这些面片对应于地图上的三角形。

输入的第一行包含一个整数 $t$ $(1 \leq t \leq 10000)$，表示测试用例的数量。接下来是 $t$ 个测试用例的描述。

每个测试用例的第一行包含四个整数 $w, \ell, n, m$，其中 $w$ $(1 \leq w \leq 10^{6})$ 是边境地带从西到东的范围，$\ell$ $(1 \leq \ell \leq 10^{6})$ 是从南到北的范围，$n$ $(4 \leq n \leq 50000)$ 是顶点的数量，$m$ $(n-2 \leq m \leq 2 n-6)$ 是所提供三角剖分中三角形的数量。

接下来是 $n$ 行，第 $i$ 行包含三个整数 $x_{i}, y_{i}, z_{i}$ $(0 \leq x_{i} \leq w; 0 \leq y_{i} \leq \ell; 0 \leq z_{i} \leq 10^{6})$，表示顶点 $i$ 的坐标和海拔高度。只有四个角点的 $x_i$ 值为 $0$ 或 $w$。所有的坐标对 $(x_{i}, y_{i})$ 都是唯一的。所有的 $z_{i}$ 值都是唯一的。

接下来的 $m$ 行每行包含三个不同的整数 $a, b, c$ $(1 \leq a, b, c \leq n)$，表示一个由顶点 $a, b, c$ 以逆时针顺序形成的地图三角形。这些三角形是对矩形 $[0, w] \times [0, \ell]$ 的完整三角剖分。$n$ 个顶点中的每一个都至少被一个三角形引用。

所有测试用例的 $n$ 的总和最多为 $50000$。

输出格式

对于每个测试用例，如果可以在单一海拔高度上构建一条连接西部边界和东部边界的熔岩护城河，则输出这样一条护城河的最小长度，绝对或相对误差不超过 $10^{-6}$。否则，输出 impossible。

样例

输入

3
6 6 4 2
0 0 1
6 0 4
6 6 3
0 6 2
1 2 3
1 3 4
6 6 4 2
0 0 1
6 0 2
6 6 4
0 6 3
1 2 3
1 3 4
10 6 7 7
6 1 8
10 0 10
10 6 4
2 6 6
0 6 0
4 3 11
0 0 7
2 1 7
2 3 1
3 6 1
3 4 6
6 4 5
5 7 6
7 1 6

输出

impossible
6.708203932
15.849260054