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

C. Crane Balancing

Wherever there is large-scale construction, you will find cranes that do the lifting. One hardly ever thinks about what marvelous examples of engineering cranes are: a structure of (relatively) little weight that can lift much heavier loads. But even the be...

Updated May 21, 2026
Track ICPC
Year 2014
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
Time limit 1 second

Wherever there is large-scale construction, you will find cranes that do the lifting. One hardly ever thinks about what marvelous examples of engineering cranes are: a structure of (relatively) little weight that can lift much heavier loads. But even the best-built cranes may have a limit on how much weight they can lift. The Association of Crane Manufacturers (ACM) needs a program to compute the range of weights that a crane can lift. Since cranes are symmetric, ACM engineers have decided to consider only a cross section of each crane, which can be viewed as a polygon resting on the x-axis.

Figure C.1: Crane cross section

Figure C.1 shows a cross section of the crane in the first sample input. Assume that every 1 × 1 unit of crane cross section weighs 1 kilogram and that the weight to be lifted will be attached at one of the polygon vertices (indicated by the arrow in Figure C.1). Write a program that determines the weight range for which the crane will not topple to the left or to the right.

Input

The input consists of a single test case. The test case starts with a single integer n (3 ≤ n ≤ 100), the number of points of the polygon used to describe the crane’s shape. The following n pairs of integers xi , yi (−2 000 ≤ xi ≤ 2 000, 0 ≤ yi ≤ 2 000) are the coordinates of the polygon points in order. The weight is attached at the first polygon point and at least two polygon points are lying on the x-axis.

Output

Display the weight range (in kilograms) that can be attached to the crane without the crane toppling over. If the range is [a, b], display bac .. dbe. For example, if the range is [1.5, 13.3], display 1 .. 14. If the range is [a, ∞), display bac .. inf. If the crane cannot carry any weight, display unstable instead.

Sample Tests

Sample 1
Sample Input 
7
50 50
0 50
0 0
30 0
30 30
40 40
50 40
Sample Output 
0 .. 1017
Sample 2
Sample Input 
7
50 50
0 50
0 0
10 0
10 30
20 40
50 40
Sample Output 
unstable
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/2014/C-crane-balancing/solution.texC++ implementationcompetitive_programming/icpc/2014/C-crane-balancing/solution.cppStatement textcompetitive_programming/icpc/2014/C-crane-balancing/statement.txtStatement PDFcompetitive_programming/icpc/2014/C-crane-balancing/statement.pdfMetadatacompetitive_programming/icpc/2014/C-crane-balancing/meta.jsonYear packetcompetitive_programming/icpc/2014/contest_problems.pdf