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

H. Single Cut of Failure

The Intrusion and Crime Prevention Company (ICPC) builds intrusion detection systems for homes and businesses. The International Collegiate Programming Contest (in a strange coincidence also known as ICPC) is considering hiring the company to secure the roo...

Updated May 21, 2026
Track ICPC
Year 2018
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 6 seconds

The Intrusion and Crime Prevention Company (ICPC) builds intrusion detection systems for homes and businesses. The International Collegiate Programming Contest (in a strange coincidence also known as ICPC) is considering hiring the company to secure the room that contains the problem set for next year’s World Finals. The contest staff wants to prevent the intrusion attempts that were made in past years, such as rappelling down the outside of the building to enter through a window, crawling through air ducts, impersonating Bill Poucher, and the creative use of an attack submarine. For that reason, the problems will be stored in a room that has a single door and no other exits. ICPC (the company) proposes to install sensors on the four sides of the door, where pairs of sensors are connected by wires. If somebody opens the door, any connected sensor pair will detect this and cause an alarm to sound. The system has one design flaw, however. An intruder might cut the wires before opening the door. To assess the security of the system, you need to determine the minimum number of line segments that cut all wires. Figure H.1 shows two configurations of wires on the door (corresponding to the two sample inputs), and minimum-size cuts that intersect all wires.

(a) Four wires (blue) that can be                   (b) Five wires that need two cuts.
intersected with a single cut (red).
Figure H.1: Illustrations of Sample Inputs 1 and 2.

Input

The input starts with a line containing three integers n, w, and h, which represent the number of wires installed (1 ≤ n ≤ 106 ) and the dimensions of the door (1 ≤ w, h ≤ 108 ). This is followed by n lines, each describing a wire placement. Each of these lines contains four integers x1 , y1 , x2 , and y2 (0 ≤ x1 , x2 ≤ w, 0 ≤ y1 , y2 ≤ h), meaning that a wire goes from (x1 , y1 ) to (x2 , y2 ). Each wire connects different sides of the door. No wire is anchored to any of the four corners of the door. All locations in the input are distinct.

Output

Display a minimum-size set of straight line cuts that intersect all wires. First, display the number of cuts needed. Then display the cuts, one per line in the format x1 y1 x2 y2 for the cut between (x1 , y1 ) and (x2 , y2 ). Each cut has to start and end on different sides of the door. Cuts cannot start or end closer than 10−6 to any wire anchor location or any corner of the door. Cuts may be displayed in any order. The start and end locations of each cut may be displayed in either order. If there are multiple sets of cuts with the same minimum size, display any of them.

Sample Tests

Sample 1
Sample Input 
 4   4   6
 0   1   4   4
 0   5   2   0
 0   3   3   6
 2   6   4   2
Sample Output 
1
0 4 4 3
Sample 2
Sample Input 
 5   4   6
 0   2   2   0
 0   3   2   6
 1   6   3   0
 1   0   4   4
 3   6   4   2
Sample Output 
2
0 4 4 4.5
0 1 4 1
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/2018/H-single-cut-of-failure/solution.texC++ implementationcompetitive_programming/icpc/2018/H-single-cut-of-failure/solution.cppStatement textcompetitive_programming/icpc/2018/H-single-cut-of-failure/statement.txtStatement PDFcompetitive_programming/icpc/2018/H-single-cut-of-failure/statement.pdfMetadatacompetitive_programming/icpc/2018/H-single-cut-of-failure/meta.jsonYear packetcompetitive_programming/icpc/2018/contest_problems.pdf