G. Lava Moat
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 w...
Problem Statement
Formatted from the contest statement text, with sample tests broken out into copyable blocks.
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.
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 Tests
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 6impossible
6.708203932
15.849260054Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
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
C++ solution used for this page.
#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 and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.
Show raw files
competitive_programming/icpc/2025/G-lava-moat/solution.texC++ implementationcompetitive_programming/icpc/2025/G-lava-moat/solution.cppStatement textcompetitive_programming/icpc/2025/G-lava-moat/statement.txtStatement PDFcompetitive_programming/icpc/2025/G-lava-moat/statement.pdfMetadatacompetitive_programming/icpc/2025/G-lava-moat/meta.jsonYear packetcompetitive_programming/icpc/2025/contest_problems.pdf