P14286 [ICPC 2025 WF] Lava Moat

这些讨厌的正义军队又要来打扰地精们安静和平的土地了。建造一堵巨大的墙并没有奏效，因此地精们打算采用久经考验的防御手段：挖一条充满岩浆的护城河。他们想把这条护城河作为北方地精领地和南方正义军领地之间的边界，从西到东横穿整个边境地带。 这对他们来说提出了一个挑战。边境地区地势多变，有丘陵甚至是山地，而岩浆护城河必须保持同一高程——否则高处的岩浆会流到低处并从护城河流出。因此，地精们必须选择一条完全位于同一高程上的路径，把边境地带的西部边界与东部边界连接起来。出于经济原因，他们希望这条路径尽可能短。 这正是你需要出场的地方。你将得到边境地带的高程地图，你的任务是确定这条护城河最短能有多长。 地图以完全三角剖分的矩形给出，尺寸为 $w \times \ell$，所有三角形均为正面积。没有顶点落在其它三角形边的内部。地图的西南角为坐标 $(0, 0)$，$x$ 轴向东，$y$ 轴向北。此外，西部边界（连接 $(0,0)$ 与 $(0,\ell)$ 的线段，包括端点）是单条边。东部边界（连接 $(w, 0)$ 和 $(w, \ell)$ 的线段，包括端点）同样如此。 当然，这份地图只是实际三维地形的二维投影：每个 $(x, y)$ 点还有一个高程 $z$。三角剖分顶点的高程直接由地图指定，且所有给定的高程两两不同。任意其它点的高程可通过其所在三角形线性插值得到。换句话说，地形由多个三角形面片拼接而成，这些面片通过公共边连接。这些面片对应于地图中的三角形。 :::align{center}  图 G.1：示例测试用例的插图。阴影表示高程，红色粗线表示最优护城河。 :::

第一行输入一个整数 $t$（$1 \le t \le 10\,000$），表示测试用例的数量。接下来的 $t$ 组测试用例描述如下。 每个测试用例的第一行包含四个整数 $w$、$\ell$、$n$ 和 $m$，其中 $w$（$1 \le w \le 10^6$）表示西到东的边境长度，$\ell$（$1 \le \ell \le 10^6$）表示南到北的边境长度，$n$（$4 \le n \le 50\,000$）为顶点数，$m$（$n - 2 \le m \le 2n - 6$）为三角形数。 接下来 $n$ 行描述顶点信息，第 $i$ 行包含三个整数 $x_i$、$y_i$、$z_i$（$0 \le x_i \le w$；$0 \le y_i \le \ell$；$0 \le z_i \le 10^6$），表示第 $i$ 个顶点的坐标和高程。仅有四个角的顶点会满足 $x_i=0$ 或 $x_i=w$。所有 $(x_i, y_i)$ 互不相同，所有 $z_i$ 也互不相同。 之后 $m$ 行，每行包含三个不同的整数 $a$、$b$、$c$（$1 \le a, b, c \le n$），表示由顶点 $a$、$b$、$c$ 按逆时针顺序组成的一个地图三角形。这些三角形共同完全三角剖分了矩形 $[0,w] \times [0,\ell]$。每个顶点至少会被一个三角形引用。 所有测试用例中，$n$ 的总和不超过 $50\,000$。

对于每个测试用例，如果可能构建一条高程一致、连接西部至东部边界的岩浆护城河，则输出最短长度，要求绝对误差或相对误差不超过 $10^{-6}$。如果无法实现，则输出 `impossible`。

由 ChatGPT 5 翻译