EP Ethan Pham Project Euler, competitive programming, and notes on the things I keep studying.
ICPC 2010
ICPC 2010

H. Rain

Problem ID: rain In recent years, hurricanes and tsunamis have shown the destructive power of water. That destructive power is not restricted to the sea, however. Heavy rain may cause floods, destroying people’s houses and fields. Using intricate models, sc...

Updated May 21, 2026
Track ICPC
Year 2010
Statement Text + PDF
TeXC++Statement textStatement PDF
Problem statement

Problem Statement

Formatted from the contest statement text, with sample tests broken out into copyable blocks.

Statement text Statement PDF

In recent years, hurricanes and tsunamis have shown the destructive power of water. That destructive power is not restricted to the sea, however. Heavy rain may cause floods, destroying people’s houses and fields. Using intricate models, scientists try to predict where the water will accumulate as a result of significant rain.

One of the ways to model a hilly landscape is triangulation, which approximates a surface using triangles. Triangle sides are entirely shared between two adjacent triangles, with the exception of triangles at the region boundary, which may have some sides not shared.

Imagine you have a triangulation model of a landscape. Now the rain starts pouring down – some water flows to the sea, and the rest gets trapped by the landscape to form lakes. Your task is to write a program that determines how many lakes are formed and the water level in each of them. Assume that the rain is heavy enough to fill all lakes up to their maximal levels.

For any lake, it is possible to sail between any two points on its surface (except the boundaries) with a boat whose size is arbitrarily small, but not zero. Therefore, if two lakes share only points (or one point) having a zero depth, they are considered different lakes.

Input

The input contains several test cases. Each test case starts with a line containing two integers, p ≥ 3, which is the number of points, and s ≥ 3, which is the number of sides of the triangulation. Each of the next p lines describes a triangulation point.

The description of each point starts with a two-letter code that is unique for the test case. The code is followed by three integers that describe the point in the format x y h. Here x and y (-10000 ≤ x,y ≤ 10000) are two- dimensional coordinates and h (0 ≤ h ≤ 8848) is the height of the point above sea level.

Each of the next s lines contains the description of one side of a triangle. The description of a side consists of two different two-letter codes that specify the endpoints of the side. The projection of the lines to the xy-plane satisfies the following conditions:

  • No side intersects any other side except at its endpoints.
  • The points and sides together form a triangulation of a single connected region.
  • There are no “holes” inside the region (that is, the boundary forms a single closed polygonal curve).

You may consider all points outside the triangulated region to have lower heights than the closest point of the region boundary. In other words, if the water gets to a boundary of the region, it flows out freely.

The last line of the input contains two zeroes.

Output

For each test case, display the case number and the levels of all different lakes located inside the given region, each on a separate line. The levels are heights above sea level and should be printed in non-decreasing order. If no lakes are formed display a single 0. Follow the format of the sample output.

Sample Tests

Sample
Sample Input 
3 3
AA 0 0 0
BB 0 1 0
CC 1 0 0
AA BB
AA CC
BB CC
7 12
aa 1 1 5
bb 1 3 5
xX 0 2 10
XY 0 4 15
XZ 3 4 11
xy 0 0 15
xz 3 0 15
xX XZ
XY XZ
xX XY
xX xy
xX xz
xz xy
aa xX
aa xy
aa xz
bb xX
bb XY
bb XZ
0 0
Sample Output 
Case 1:
0
Case 2:
10
10
Editorial

Editorial

The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.

Raw TeX

Key Observations

  • Write the structural observations that make the problem tractable.

  • State any useful invariant, monotonicity property, graph interpretation, or combinatorial reformulation.

  • If the constraints matter, explain exactly which part of the solution they enable.

Algorithm

  1. Describe the data structures and the state maintained by the algorithm.

  2. Explain the processing order and why it is sufficient.

  3. Mention corner cases explicitly if they affect the implementation.

Correctness Proof

We prove that the algorithm returns the correct answer.

Lemma 1.

State the first key claim.

Proof.

Provide a concise proof.

Lemma 2.

State the next claim if needed.

Proof.

Provide a concise proof.

Theorem.

The algorithm outputs the correct answer for every valid input.

Proof.

Combine the lemmas and finish the argument.

Complexity Analysis

State the running time and memory usage in terms of the input size.

Implementation Notes

  • Mention any non-obvious implementation detail that is easy to get wrong.

  • Mention numeric limits, indexing conventions, or tie-breaking rules if relevant.

Implementation

Code

C++ solution used for this page.

C++

Clean code view with a raw-file link when you want the original source.

Raw file 
#include <bits/stdc++.h>
using namespace std;

namespace {

void solve() {
    // Fill in the full solution logic for the problem here.
}

}  // namespace

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
    return 0;
}
Resources

Source Files and Assets

Raw files are still available here when you want the original TeX, C++, or statement assets.

Show raw files
TeX write-upcompetitive_programming/icpc/2010/H-rain/solution.texC++ implementationcompetitive_programming/icpc/2010/H-rain/solution.cppStatement textcompetitive_programming/icpc/2010/H-rain/statement.txtStatement PDFcompetitive_programming/icpc/2010/H-rain/statement.pdfMetadatacompetitive_programming/icpc/2010/H-rain/meta.jsonYear packetcompetitive_programming/icpc/2010/contest_problems.pdf