ICPC 2025 - G. Lava Moat
For a chosen elevation c, the lava moat must follow the contour line where the terrain has height c. We must find the shortest such contour path that connects the western border edge of the rectangle to the eastern bo...
Source-first archive entry
This page is built from the copied files in competitive_programming/icpc/2025/G-lava-moat. Edit
competitive_programming/icpc/2025/G-lava-moat/solution.tex to update the written solution and
competitive_programming/icpc/2025/G-lava-moat/solution.cpp to update the implementation.
The website does not replace those files with hand-maintained HTML. It reads the copied source tree during the build and exposes the exact files below.
Problem Statement
Copied statement text kept beside the solution archive for direct reference.
Problem G
Lava Moat
Time limit: 4 seconds
These pesky armies of good are coming to disturb the quiet and peaceful lands of the goblins again.
Building a huge wall didn’t work out that well, and so the goblins are going to turn to the tried and true
staple of defense: a moat filled with lava. They want to dig this moat as a boundary between the goblin
lands in the north and the do-gooder lands in the south, crossing the whole borderlands west-to-east.
This presents them with a challenge. The borderlands are hilly, if not outright mountainous, while a lava
moat has to be all on one level – otherwise the lava from the higher parts will flow down and out of the
moat in the lower parts. So, the goblins have to choose a path that is all on one elevation, and connects
the western border of the borderlands to its eastern border. For obvious economic reasons, they want
this path to be as short as possible.
This is where you come in. You are given an elevation map of the borderlands, and your task is to
determine how short the moat can be.
The map is in the form of a fully triangulated rectangle with dimensions w × ℓ, with all triangles having
positive area. No vertex of a triangle lies on the interior of an edge of another triangle. The southwestern
corner of the map has coordinates (0, 0), with the x-axis going east and the y-axis going north. Further-
more, the western border (the line segment connecting (0, 0) and (0, ℓ), including the endpoints) is a
single edge. Similarly, the eastern border (between points (w, 0) and (w, ℓ)) is also a single edge.
Of course, this map is just a 2D projection of the actual 3D terrain: Every point (x, y) also has an
elevation z. The elevation at the vertices of the triangulation is directly specified by the map, and
all of these given elevations are distinct. The elevation at all other points can be computed by linear
interpolation on associated triangles. In other words, the terrain is shaped like a collection of triangular
faces joined together by shared sides. These faces correspond to the triangles on the map.
Figure G.1: Illustration of the sample test cases. Shading denotes elevation, and the thick
red lines denote optimal moats.
Input
The first line of input contains an integer t (1 ≤ t ≤ 10 000), which is the number of test cases. The
descriptions of t test cases follow.
The first line of each test case contains four integers w, ℓ, n, and m, where w (1 ≤ w ≤ 106 ) is
the extent of the borderlands from west to east, ℓ (1 ≤ ℓ ≤ 106 ) is the extent from south to north,
n (4 ≤ n ≤ 50 000) is the number of vertices, and m (n − 2 ≤ m ≤ 2n − 6) is the number of triangles
in the provided triangulation.
49th ICPC World Championship Problem G: Lava Moat © ICPC Foundation 13
This is followed by n lines, the ith of which contains three integers xi , yi , and zi (0 ≤ xi ≤ w;
0 ≤ yi ≤ ℓ; 0 ≤ zi ≤ 106 ), denoting the coordinates and the elevation of vertex i. The only vertices
with xi = 0 or xi = w are the four corners. All pairs (xi , yi ) are distinct. All zi s are distinct.
Each of the following m lines contains three distinct integers a, b, and c (1 ≤ a, b, c ≤ n), denoting a
map triangle formed by vertices a, b, and c in counter-clockwise order. These triangles are a complete
triangulation of the rectangle [0, w] × [0, ℓ]. Each of the n vertices is referenced by at least one triangle.
Over all test cases, the sum of n is at most 50 000.
Output
For each test case, if it is possible to construct a lava moat at a single elevation that connects the western
border to the eastern border, output the minimum length of such a moat, with an absolute or relative
error of at most 10−6 . Otherwise, output impossible.
Sample Input 1 Sample Output 1
3 impossible
6 6 4 2 6.708203932
0 0 1 15.849260054
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
49th ICPC World Championship Problem G: Lava Moat © ICPC Foundation 14
Editorial
Rendered from the copied solution.tex file. The original TeX source remains
available below.
Key Observations
Fix an elevation $c$ that is not equal to any vertex height. In each triangle, the intersection with the horizontal plane $z=c$ is either empty or a single line segment joining the two triangle edges whose endpoints lie on opposite sides of the level.
As $c$ moves between two consecutive vertex heights, the combinatorial structure of these contour segments does not change. Only their lengths change, and inside one triangle that length is a linear function of $c$.
Therefore every connected contour component in such an interval has total length of the form $A c + B$. A minimum over a linear function on an interval is attained at an endpoint, so it is enough to inspect levels equal to vertex heights.
A contour component is built by gluing triangle-edge crossings together. This suggests a DSU on triangulation edges rather than on vertices. When a triangle is active in a whole interval of elevations, it contributes one linear-length segment joining two crossing edges, so within that interval we should union those two edge components and add that segment length.
A triangle is active on one or two disjoint intervals of the sorted vertex heights. These intervals can be inserted into a segment tree over the height order and processed with a rollback DSU.
Algorithm
Sort all vertices by height. Each leaf of the segment tree corresponds to one vertex height.
For every triangle, determine the height intervals in which the contour crosses that triangle. On each such interval, identify the two crossed triangle edges and compute the segment length in the form $a c + b$. Insert this ``active segment'' into the segment tree interval.
Traverse the segment tree with a rollback DSU on triangulation edges. Each DSU component stores the sum of its currently active contour lengths in the form $A c + B$.
At a leaf with elevation $c$:
if the west border edge and east border edge are already in the same DSU component, that component itself is a candidate moat;
otherwise, the only new connection that can appear exactly at this height is through the leaf vertex. For every incident triangle we test whether the contour at level $c$ connects the vertex to the opposite triangle edge, compute that short segment length, and combine it with the best DSU component lengths reaching the west and east sides.
The minimum candidate over all leaves is the answer. enumerate
Correctness Proof
We prove that the algorithm returns the correct answer.
Lemma 1.
Between two consecutive vertex heights, the set of crossed edges in every triangle is fixed, and every active triangle contributes a contour segment whose length is linear in the elevation $c$.
Proof.
Inside one triangle, the terrain is an affine function of $(x,y)$. Intersecting an affine plane with the horizontal plane $z=c$ produces a line. As long as $c$ stays strictly between the same two vertex heights, the line meets the same pair of triangle edges, so the contour segment endpoints move linearly along those edges. Hence the segment length is linear in $c$. □
Lemma 2.
For any open interval between consecutive vertex heights, the total length of every connected contour component is a linear function of $c$ on that interval.
Proof.
By Lemma 1, each active triangle contributes one linear-length segment throughout the interval. The contour connectivity does not change inside the interval because no triangle changes its crossed edges. Therefore a connected component is always the union of the same set of triangle segments, and its total length is the sum of linear functions, hence linear. □
Lemma 3.
Some optimal moat is attained at a vertex height.
Proof.
Take any interval between consecutive vertex heights. By Lemma 2, every contour component length on that interval is linear in $c$, so the minimum value of any fixed candidate path is attained at one of the two endpoints of the interval. Since every feasible moat belongs to one of these candidates, an overall optimum exists at a vertex height. □
Theorem.
The algorithm outputs the correct answer for every valid input.
Proof.
By Lemma 3 it is enough to inspect vertex heights. For one such height $c$, the rollback DSU contains exactly the contour segments that remain active up to that leaf, with exactly the correct length expressions, so every already-connected west-to-east contour component is evaluated correctly. If west and east are not already in the same component, the only new topological event at level $c$ can occur at the vertex whose height equals $c$. The per-triangle checks performed at the leaf enumerate all ways in which the contour can leave that vertex and join an already maintained DSU component. Combining one such branch on the west side and one on the east side gives every possible moat passing through that vertex, and no other new connection can appear at this exact height. Therefore every feasible moat is considered and evaluated with its exact length, so the minimum printed by the algorithm is the true optimum. □
Complexity Analysis
Let $n$ be the number of vertices and $m$ the number of triangles. Each triangle contributes $O(1)$ active intervals, each interval is inserted into the segment tree in $O(\log n)$ nodes, and each inserted segment causes one rollback-DSU union. Hence the total running time is $O((n+m)\log n)$, and the memory usage is $O((n+m)\log n)$ for the segment tree plus $O(n+m)$ for the geometric data and the DSU.
Implementation Notes
The DSU is built on triangulation edges because contour segments connect edge crossings, not vertices.
Rollback is essential: the same active contour segment belongs to many segment-tree nodes, so we need to undo unions when returning from recursion.
All geometry is done with doubles; the required error tolerance is generous enough for this.
Code
Exact copied C++ implementation from solution.cpp.
#include <bits/stdc++.h>
using namespace std;
struct Vertex {
long double x, y, z;
};
struct Triangle {
array<int, 3> v;
array<int, 3> e;
};
struct ContourPiece {
int e1, e2;
long double slope, intercept;
};
struct RollbackDSU {
struct Change {
int child;
int parent_root;
int old_size;
long double old_slope;
long double old_intercept;
};
vector<int> parent, sz;
vector<long double> slope_sum, intercept_sum;
vector<Change> history;
void init(int n) {
parent.resize(n);
sz.assign(n, 1);
slope_sum.assign(n, 0);
intercept_sum.assign(n, 0);
history.clear();
iota(parent.begin(), parent.end(), 0);
}
int find(int x) {
while (parent[x] != x) {
x = parent[x];
}
return x;
}
int snapshot() const {
return (int)history.size();
}
void unite(int a, int b, long double add_slope, long double add_intercept) {
a = find(a);
b = find(b);
if (a == b) {
return;
}
if (sz[a] < sz[b]) {
swap(a, b);
}
history.push_back({b, a, sz[a], slope_sum[a], intercept_sum[a]});
parent[b] = a;
sz[a] += sz[b];
slope_sum[a] += slope_sum[b] + add_slope;
intercept_sum[a] += intercept_sum[b] + add_intercept;
}
void rollback(int snap) {
while ((int)history.size() > snap) {
Change step = history.back();
history.pop_back();
parent[step.child] = step.child;
sz[step.parent_root] = step.old_size;
slope_sum[step.parent_root] = step.old_slope;
intercept_sum[step.parent_root] = step.old_intercept;
}
}
long double component_length(int x, long double level) {
x = find(x);
return slope_sum[x] * level + intercept_sum[x];
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
cout << fixed << setprecision(9);
while (t--) {
int w, h, n, m;
cin >> w >> h >> n >> m;
vector<Vertex> vertex(n + 1);
int sw = -1, se = -1, nw = -1, ne = -1;
for (int i = 1; i <= n; ++i) {
int x, y, z;
cin >> x >> y >> z;
vertex[i] = {(long double)x, (long double)y, (long double)z};
if (x == 0 && y == 0) sw = i;
if (x == w && y == 0) se = i;
if (x == 0 && y == h) nw = i;
if (x == w && y == h) ne = i;
}
long double low_ok =
max(min(vertex[sw].z, vertex[nw].z), min(vertex[se].z, vertex[ne].z));
long double high_ok =
min(max(vertex[sw].z, vertex[nw].z), max(vertex[se].z, vertex[ne].z));
auto edge_key = [](int a, int b) -> unsigned long long {
if (a > b) swap(a, b);
return (unsigned long long)(unsigned int)a << 32 | (unsigned int)b;
};
unordered_map<unsigned long long, int> edge_id;
edge_id.reserve(3 * m + 10);
vector<pair<int, int>> edges;
edges.reserve(3 * m);
auto get_or_create_edge = [&](int a, int b) {
unsigned long long key = edge_key(a, b);
auto it = edge_id.find(key);
if (it != edge_id.end()) {
return it->second;
}
int id = (int)edges.size();
edges.push_back({min(a, b), max(a, b)});
edge_id[key] = id;
return id;
};
vector<Triangle> tri(m);
vector<vector<int>> incident(n + 1);
for (int i = 0; i < m; ++i) {
int a, b, c;
cin >> a >> b >> c;
tri[i] = {{{a, b, c}}, {{get_or_create_edge(a, b), get_or_create_edge(b, c),
get_or_create_edge(c, a)}}};
incident[a].push_back(i);
incident[b].push_back(i);
incident[c].push_back(i);
}
auto lookup_edge = [&](int a, int b) {
return edge_id.at(edge_key(a, b));
};
int west_edge = lookup_edge(sw, nw);
int east_edge = lookup_edge(se, ne);
vector<int> order(n);
iota(order.begin(), order.end(), 1);
sort(order.begin(), order.end(), [&](int a, int b) { return vertex[a].z < vertex[b].z; });
vector<int> rank(n + 1);
for (int i = 0; i < n; ++i) {
rank[order[i]] = i;
}
int base = 1;
while (base < n) {
base <<= 1;
}
vector<vector<ContourPiece>> seg(2 * base);
auto add_range = [&](int l, int r, const ContourPiece& piece) {
for (l += base, r += base; l < r; l >>= 1, r >>= 1) {
if (l & 1) seg[l++].push_back(piece);
if (r & 1) seg[--r].push_back(piece);
}
};
auto contour_norm = [&](int pivot, int a, int b) {
const Vertex& s = vertex[pivot];
const Vertex& p = vertex[a];
const Vertex& q = vertex[b];
long double dx = (p.x - s.x) / (p.z - s.z) - (q.x - s.x) / (q.z - s.z);
long double dy = (p.y - s.y) / (p.z - s.z) - (q.y - s.y) / (q.z - s.z);
return hypotl(dx, dy);
};
for (const Triangle& cur : tri) {
array<int, 3> ord = {0, 1, 2};
sort(ord.begin(), ord.end(), [&](int lhs, int rhs) {
return vertex[cur.v[lhs]].z < vertex[cur.v[rhs]].z;
});
int lo = ord[0];
int mid = ord[1];
int hi = ord[2];
int low_v = cur.v[lo];
int mid_v = cur.v[mid];
int high_v = cur.v[hi];
int l = rank[low_v] + 1;
int r = rank[mid_v];
if (l < r) {
long double k = contour_norm(low_v, mid_v, high_v);
add_range(l, r, {cur.e[lo], cur.e[(lo + 2) % 3], k, -vertex[low_v].z * k});
}
l = rank[mid_v] + 1;
r = rank[high_v];
if (l < r) {
long double k = contour_norm(high_v, low_v, mid_v);
add_range(l, r,
{cur.e[hi], cur.e[(hi + 2) % 3], -k, vertex[high_v].z * k});
}
}
RollbackDSU dsu;
dsu.init((int)edges.size());
const long double INF = 1e100L;
long double answer = INF;
function<void(int, int, int)> dfs = [&](int node, int l, int r) {
int snap = dsu.snapshot();
for (const ContourPiece& piece : seg[node]) {
dsu.unite(piece.e1, piece.e2, piece.slope, piece.intercept);
}
if (r - l == 1) {
if (l < n) {
int v = order[l];
long double level = vertex[v].z;
if (low_ok <= level && level <= high_ok) {
int west_root = dsu.find(west_edge);
int east_root = dsu.find(east_edge);
long double best_here = INF;
if (west_root == east_root) {
best_here = dsu.component_length(west_root, level);
}
long double best_from_west = INF;
long double best_from_east = INF;
if (v == sw || v == nw) best_from_west = 0;
if (v == se || v == ne) best_from_east = 0;
for (int tid : incident[v]) {
const Triangle& cur = tri[tid];
int pos = 0;
while (cur.v[pos] != v) {
++pos;
}
int a = cur.v[(pos + 1) % 3];
int b = cur.v[(pos + 2) % 3];
long double da = vertex[a].z - level;
long double db = vertex[b].z - level;
if (!((da < 0 && db > 0) || (da > 0 && db < 0))) {
continue;
}
int opp_edge = cur.e[(pos + 1) % 3];
long double t_on_edge =
(level - vertex[a].z) / (vertex[b].z - vertex[a].z);
long double px =
vertex[a].x + t_on_edge * (vertex[b].x - vertex[a].x);
long double py =
vertex[a].y + t_on_edge * (vertex[b].y - vertex[a].y);
long double extra = hypotl(px - vertex[v].x, py - vertex[v].y);
int root = dsu.find(opp_edge);
if (root == west_root) {
long double base_cost =
(opp_edge == west_edge ? 0 : dsu.component_length(root, level));
best_from_west = min(best_from_west, base_cost + extra);
}
if (root == east_root) {
long double base_cost =
(opp_edge == east_edge ? 0 : dsu.component_length(root, level));
best_from_east = min(best_from_east, base_cost + extra);
}
}
if (best_from_west < INF / 2 && best_from_east < INF / 2) {
best_here = min(best_here, best_from_west + best_from_east);
}
answer = min(answer, best_here);
}
}
} else {
int mid = (l + r) / 2;
dfs(node * 2, l, mid);
dfs(node * 2 + 1, mid, r);
}
dsu.rollback(snap);
};
dfs(1, 0, base);
if (answer >= INF / 2) {
cout << "impossible\n";
} else {
cout << answer << '\n';
}
}
return 0;
}
Source Files
Exact copied source-of-truth files. Edit solution.tex for the write-up and solution.cpp for the implementation.
\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{enumitem}
\title{ICPC World Finals 2025\\G. Lava Moat}
\author{}
\date{}
\begin{document}
\maketitle
\section*{Problem Summary}
For a chosen elevation $c$, the lava moat must follow the contour line where the terrain has height $c$.
We must find the shortest such contour path that connects the western border edge of the rectangle to the
eastern border edge, or determine that no contour of any elevation can do so.
\section*{Key Observations}
\begin{itemize}[leftmargin=*]
\item Fix an elevation $c$ that is not equal to any vertex height.
In each triangle, the intersection with the horizontal plane $z=c$ is either empty or a single line
segment joining the two triangle edges whose endpoints lie on opposite sides of the level.
\item As $c$ moves between two consecutive vertex heights, the combinatorial structure of these contour
segments does not change. Only their lengths change, and inside one triangle that length is a linear
function of $c$.
\item Therefore every connected contour component in such an interval has total length of the form
$A c + B$.
A minimum over a linear function on an interval is attained at an endpoint, so it is enough to inspect
levels equal to vertex heights.
\item A contour component is built by gluing triangle-edge crossings together.
This suggests a DSU on triangulation edges rather than on vertices.
When a triangle is active in a whole interval of elevations, it contributes one linear-length segment
joining two crossing edges, so within that interval we should union those two edge components and add
that segment length.
\item A triangle is active on one or two disjoint intervals of the sorted vertex heights.
These intervals can be inserted into a segment tree over the height order and processed with a rollback
DSU.
\end{itemize}
\section*{Algorithm}
\begin{enumerate}[leftmargin=*]
\item Sort all vertices by height. Each leaf of the segment tree corresponds to one vertex height.
\item For every triangle, determine the height intervals in which the contour crosses that triangle.
On each such interval, identify the two crossed triangle edges and compute the segment length in the
form $a c + b$. Insert this ``active segment'' into the segment tree interval.
\item Traverse the segment tree with a rollback DSU on triangulation edges.
Each DSU component stores the sum of its currently active contour lengths in the form $A c + B$.
\item At a leaf with elevation $c$:
\begin{itemize}[leftmargin=*]
\item if the west border edge and east border edge are already in the same DSU component, that
component itself is a candidate moat;
\item otherwise, the only new connection that can appear exactly at this height is through the leaf
vertex.
For every incident triangle we test whether the contour at level $c$ connects the vertex to the
opposite triangle edge, compute that short segment length, and combine it with the best DSU
component lengths reaching the west and east sides.
\end{itemize}
\item The minimum candidate over all leaves is the answer.
\end{enumerate}
\section*{Correctness Proof}
We prove that the algorithm returns the correct answer.
\paragraph{Lemma 1.}
Between two consecutive vertex heights, the set of crossed edges in every triangle is fixed, and every
active triangle contributes a contour segment whose length is linear in the elevation $c$.
\paragraph{Proof.}
Inside one triangle, the terrain is an affine function of $(x,y)$. Intersecting an affine plane with the
horizontal plane $z=c$ produces a line. As long as $c$ stays strictly between the same two vertex heights,
the line meets the same pair of triangle edges, so the contour segment endpoints move linearly along
those edges. Hence the segment length is linear in $c$. \qed
\paragraph{Lemma 2.}
For any open interval between consecutive vertex heights, the total length of every connected contour
component is a linear function of $c$ on that interval.
\paragraph{Proof.}
By Lemma 1, each active triangle contributes one linear-length segment throughout the interval.
The contour connectivity does not change inside the interval because no triangle changes its crossed edges.
Therefore a connected component is always the union of the same set of triangle segments, and its total
length is the sum of linear functions, hence linear. \qed
\paragraph{Lemma 3.}
Some optimal moat is attained at a vertex height.
\paragraph{Proof.}
Take any interval between consecutive vertex heights. By Lemma 2, every contour component length on
that interval is linear in $c$, so the minimum value of any fixed candidate path is attained at one of the
two endpoints of the interval. Since every feasible moat belongs to one of these candidates, an overall
optimum exists at a vertex height. \qed
\paragraph{Theorem.}
The algorithm outputs the correct answer for every valid input.
\paragraph{Proof.}
By Lemma 3 it is enough to inspect vertex heights.
For one such height $c$, the rollback DSU contains exactly the contour segments that remain active up to
that leaf, with exactly the correct length expressions, so every already-connected west-to-east contour
component is evaluated correctly.
If west and east are not already in the same component, the only new topological event at level $c$ can
occur at the vertex whose height equals $c$. The per-triangle checks performed at the leaf enumerate all
ways in which the contour can leave that vertex and join an already maintained DSU component.
Combining one such branch on the west side and one on the east side gives every possible moat passing
through that vertex, and no other new connection can appear at this exact height.
Therefore every feasible moat is considered and evaluated with its exact length, so the minimum printed
by the algorithm is the true optimum. \qed
\section*{Complexity Analysis}
Let $n$ be the number of vertices and $m$ the number of triangles.
Each triangle contributes $O(1)$ active intervals, each interval is inserted into the segment tree in
$O(\log n)$ nodes, and each inserted segment causes one rollback-DSU union.
Hence the total running time is $O((n+m)\log n)$, and the memory usage is $O((n+m)\log n)$ for the
segment tree plus $O(n+m)$ for the geometric data and the DSU.
\section*{Implementation Notes}
\begin{itemize}[leftmargin=*]
\item The DSU is built on triangulation edges because contour segments connect edge crossings, not
vertices.
\item Rollback is essential: the same active contour segment belongs to many segment-tree nodes, so we
need to undo unions when returning from recursion.
\item All geometry is done with doubles; the required error tolerance is generous enough for this.
\end{itemize}
\end{document}
#include <bits/stdc++.h>
using namespace std;
struct Vertex {
long double x, y, z;
};
struct Triangle {
array<int, 3> v;
array<int, 3> e;
};
struct ContourPiece {
int e1, e2;
long double slope, intercept;
};
struct RollbackDSU {
struct Change {
int child;
int parent_root;
int old_size;
long double old_slope;
long double old_intercept;
};
vector<int> parent, sz;
vector<long double> slope_sum, intercept_sum;
vector<Change> history;
void init(int n) {
parent.resize(n);
sz.assign(n, 1);
slope_sum.assign(n, 0);
intercept_sum.assign(n, 0);
history.clear();
iota(parent.begin(), parent.end(), 0);
}
int find(int x) {
while (parent[x] != x) {
x = parent[x];
}
return x;
}
int snapshot() const {
return (int)history.size();
}
void unite(int a, int b, long double add_slope, long double add_intercept) {
a = find(a);
b = find(b);
if (a == b) {
return;
}
if (sz[a] < sz[b]) {
swap(a, b);
}
history.push_back({b, a, sz[a], slope_sum[a], intercept_sum[a]});
parent[b] = a;
sz[a] += sz[b];
slope_sum[a] += slope_sum[b] + add_slope;
intercept_sum[a] += intercept_sum[b] + add_intercept;
}
void rollback(int snap) {
while ((int)history.size() > snap) {
Change step = history.back();
history.pop_back();
parent[step.child] = step.child;
sz[step.parent_root] = step.old_size;
slope_sum[step.parent_root] = step.old_slope;
intercept_sum[step.parent_root] = step.old_intercept;
}
}
long double component_length(int x, long double level) {
x = find(x);
return slope_sum[x] * level + intercept_sum[x];
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
cout << fixed << setprecision(9);
while (t--) {
int w, h, n, m;
cin >> w >> h >> n >> m;
vector<Vertex> vertex(n + 1);
int sw = -1, se = -1, nw = -1, ne = -1;
for (int i = 1; i <= n; ++i) {
int x, y, z;
cin >> x >> y >> z;
vertex[i] = {(long double)x, (long double)y, (long double)z};
if (x == 0 && y == 0) sw = i;
if (x == w && y == 0) se = i;
if (x == 0 && y == h) nw = i;
if (x == w && y == h) ne = i;
}
long double low_ok =
max(min(vertex[sw].z, vertex[nw].z), min(vertex[se].z, vertex[ne].z));
long double high_ok =
min(max(vertex[sw].z, vertex[nw].z), max(vertex[se].z, vertex[ne].z));
auto edge_key = [](int a, int b) -> unsigned long long {
if (a > b) swap(a, b);
return (unsigned long long)(unsigned int)a << 32 | (unsigned int)b;
};
unordered_map<unsigned long long, int> edge_id;
edge_id.reserve(3 * m + 10);
vector<pair<int, int>> edges;
edges.reserve(3 * m);
auto get_or_create_edge = [&](int a, int b) {
unsigned long long key = edge_key(a, b);
auto it = edge_id.find(key);
if (it != edge_id.end()) {
return it->second;
}
int id = (int)edges.size();
edges.push_back({min(a, b), max(a, b)});
edge_id[key] = id;
return id;
};
vector<Triangle> tri(m);
vector<vector<int>> incident(n + 1);
for (int i = 0; i < m; ++i) {
int a, b, c;
cin >> a >> b >> c;
tri[i] = {{{a, b, c}}, {{get_or_create_edge(a, b), get_or_create_edge(b, c),
get_or_create_edge(c, a)}}};
incident[a].push_back(i);
incident[b].push_back(i);
incident[c].push_back(i);
}
auto lookup_edge = [&](int a, int b) {
return edge_id.at(edge_key(a, b));
};
int west_edge = lookup_edge(sw, nw);
int east_edge = lookup_edge(se, ne);
vector<int> order(n);
iota(order.begin(), order.end(), 1);
sort(order.begin(), order.end(), [&](int a, int b) { return vertex[a].z < vertex[b].z; });
vector<int> rank(n + 1);
for (int i = 0; i < n; ++i) {
rank[order[i]] = i;
}
int base = 1;
while (base < n) {
base <<= 1;
}
vector<vector<ContourPiece>> seg(2 * base);
auto add_range = [&](int l, int r, const ContourPiece& piece) {
for (l += base, r += base; l < r; l >>= 1, r >>= 1) {
if (l & 1) seg[l++].push_back(piece);
if (r & 1) seg[--r].push_back(piece);
}
};
auto contour_norm = [&](int pivot, int a, int b) {
const Vertex& s = vertex[pivot];
const Vertex& p = vertex[a];
const Vertex& q = vertex[b];
long double dx = (p.x - s.x) / (p.z - s.z) - (q.x - s.x) / (q.z - s.z);
long double dy = (p.y - s.y) / (p.z - s.z) - (q.y - s.y) / (q.z - s.z);
return hypotl(dx, dy);
};
for (const Triangle& cur : tri) {
array<int, 3> ord = {0, 1, 2};
sort(ord.begin(), ord.end(), [&](int lhs, int rhs) {
return vertex[cur.v[lhs]].z < vertex[cur.v[rhs]].z;
});
int lo = ord[0];
int mid = ord[1];
int hi = ord[2];
int low_v = cur.v[lo];
int mid_v = cur.v[mid];
int high_v = cur.v[hi];
int l = rank[low_v] + 1;
int r = rank[mid_v];
if (l < r) {
long double k = contour_norm(low_v, mid_v, high_v);
add_range(l, r, {cur.e[lo], cur.e[(lo + 2) % 3], k, -vertex[low_v].z * k});
}
l = rank[mid_v] + 1;
r = rank[high_v];
if (l < r) {
long double k = contour_norm(high_v, low_v, mid_v);
add_range(l, r,
{cur.e[hi], cur.e[(hi + 2) % 3], -k, vertex[high_v].z * k});
}
}
RollbackDSU dsu;
dsu.init((int)edges.size());
const long double INF = 1e100L;
long double answer = INF;
function<void(int, int, int)> dfs = [&](int node, int l, int r) {
int snap = dsu.snapshot();
for (const ContourPiece& piece : seg[node]) {
dsu.unite(piece.e1, piece.e2, piece.slope, piece.intercept);
}
if (r - l == 1) {
if (l < n) {
int v = order[l];
long double level = vertex[v].z;
if (low_ok <= level && level <= high_ok) {
int west_root = dsu.find(west_edge);
int east_root = dsu.find(east_edge);
long double best_here = INF;
if (west_root == east_root) {
best_here = dsu.component_length(west_root, level);
}
long double best_from_west = INF;
long double best_from_east = INF;
if (v == sw || v == nw) best_from_west = 0;
if (v == se || v == ne) best_from_east = 0;
for (int tid : incident[v]) {
const Triangle& cur = tri[tid];
int pos = 0;
while (cur.v[pos] != v) {
++pos;
}
int a = cur.v[(pos + 1) % 3];
int b = cur.v[(pos + 2) % 3];
long double da = vertex[a].z - level;
long double db = vertex[b].z - level;
if (!((da < 0 && db > 0) || (da > 0 && db < 0))) {
continue;
}
int opp_edge = cur.e[(pos + 1) % 3];
long double t_on_edge =
(level - vertex[a].z) / (vertex[b].z - vertex[a].z);
long double px =
vertex[a].x + t_on_edge * (vertex[b].x - vertex[a].x);
long double py =
vertex[a].y + t_on_edge * (vertex[b].y - vertex[a].y);
long double extra = hypotl(px - vertex[v].x, py - vertex[v].y);
int root = dsu.find(opp_edge);
if (root == west_root) {
long double base_cost =
(opp_edge == west_edge ? 0 : dsu.component_length(root, level));
best_from_west = min(best_from_west, base_cost + extra);
}
if (root == east_root) {
long double base_cost =
(opp_edge == east_edge ? 0 : dsu.component_length(root, level));
best_from_east = min(best_from_east, base_cost + extra);
}
}
if (best_from_west < INF / 2 && best_from_east < INF / 2) {
best_here = min(best_here, best_from_west + best_from_east);
}
answer = min(answer, best_here);
}
}
} else {
int mid = (l + r) / 2;
dfs(node * 2, l, mid);
dfs(node * 2 + 1, mid, r);
}
dsu.rollback(snap);
};
dfs(1, 0, base);
if (answer >= INF / 2) {
cout << "impossible\n";
} else {
cout << answer << '\n';
}
}
return 0;
}