Half-Plane Intersection — Contest Template

Companion to: 04-half-plane-intersection.md. That file is the conceptual lesson (directed-line convention, why the deque sweep works, full walkthrough). This file is the lean implementation reference: a single tested template plus the gotchas that bite during a contest.

Quick Revisit

• USE WHEN: finding convex feasible region from linear constraints (polygon kernel, 2D LP)
• INVARIANT: deque of half-planes maintains feasible polygon edges in angular order
• TIME: O(n log n) | SPACE: O(n)
• CLASSIC BUG: missing final cleanup pass — front of deque may become infeasible after last insertions
• PRACTICE: 08-ladder-mixed

Intersecting half-planes to find a convex feasibility region -- this is linear programming in 2D, and it solves problems from polygon kernels to optimization over linear constraints.

Difficulty: [Advanced]Prerequisites: Geometry Basics, Convex HullCF Rating Range: 1900 -- 2400

---

What Is a Half-Plane?

A line $ax+by=c$ divides the plane into two halves. A half-plane is one of those halves (including the boundary line). Every linear inequality $ax+by\le c$ defines a half-plane.

The intersection of $n$ half-planes is always a convex region -- possibly empty, a point, a line segment, a bounded polygon, or an unbounded polygon. Finding this region explicitly is the half-plane intersection problem.

  Half-plane: y <= 2x + 1

       /
      / <- boundary line
     /
    /////////
   /////////   <- feasible side (shaded)
  /////////

Why Should You Care?

• Polygon kernel: the set of points from which the entire interior of a polygon is visible. This equals the intersection of half-planes defined by the polygon's edges.
• Linear programming in 2D: optimize a linear function subject to linear constraints -- the feasible region is a half-plane intersection.
• Visibility and guard problems: "can a guard at position $p$ see every wall?" reduces to checking if $p$ is in the kernel.
• Constrained optimization on convex hulls: intersect half-planes from multiple constraint sets.

The Algorithm: Sort-and-Incremental

The standard $O(n\log n)$ approach:

1. Represent each half-plane by its boundary line, directed so the feasible side is to the left.
2. Sort half-planes by the angle of their direction vector.
3. Process them in angle order, maintaining a deque of half-planes whose intersection forms the current region.
4. When adding a new half-plane, pop from the back of the deque while the back intersection point is infeasible. Then pop from the front similarly.
5. At the end, do a final cleanup pass: the front might have become infeasible due to the last additions.

The deque invariant: consecutive half-planes in the deque intersect to form edges of the current feasible polygon, in angular order.

  Processing half-planes in angle order:

  Step 1: h1 alone       Step 2: h1 ∩ h2       Step 3: h1 ∩ h2 ∩ h3
  ============          ============          ============
  |                     |\                    |\    /|
  |  feasible           | \ feasible          | \  / |
  |                     |  \                  |  \/  |
  |                     |   \                 |  /\  |
                                              | /  feasible

Implementation

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

using ld = long double;
const ld EPS = 1e-9;

struct P { ld x, y; };
P operator-(P a, P b) { return {a.x-b.x, a.y-b.y}; }
ld cross(P a, P b) { return a.x*b.y - a.y*b.x; }

struct HalfPlane {
    P p, d; // point on line, direction vector (feasible region is to the left)
    ld angle() const { return atan2(d.y, d.x); }
};

P intersect(HalfPlane& a, HalfPlane& b) {
    ld t = cross(b.d, a.p - b.p) / cross(a.d, b.d);
    return {a.p.x + a.d.x*t, a.p.y + a.d.y*t};
}

bool outside(HalfPlane& h, P p) {
    return cross(h.d, p - h.p) < -EPS;
}

// Returns vertices of the intersection polygon (empty if infeasible)
vector<P> half_plane_intersection(vector<HalfPlane> hps) {
    sort(hps.begin(), hps.end(), [](HalfPlane& a, HalfPlane& b){
        return a.angle() < b.angle();
    });
    // remove parallel duplicates, keeping the tighter constraint
    vector<HalfPlane> unique_hps;
    for (auto& h : hps) {
        if (!unique_hps.empty() && abs(h.angle() - unique_hps.back().angle()) < EPS) {
            if (cross(h.d, unique_hps.back().p - h.p) > 0)
                unique_hps.back() = h; // h is tighter
        } else {
            unique_hps.push_back(h);
        }
    }
    hps = unique_hps;
    if ((int)hps.size() < 2) return {};

    deque<HalfPlane> dq;
    deque<P> pts;
    dq.push_back(hps[0]);
    dq.push_back(hps[1]);
    pts.push_back(intersect(dq[0], dq[1]));

    for (int i = 2; i < (int)hps.size(); i++) {
        while (!pts.empty() && outside(hps[i], pts.back())) {
            pts.pop_back(); dq.pop_back();
        }
        while (!pts.empty() && outside(hps[i], pts.front())) {
            pts.pop_front(); dq.pop_front();
        }
        dq.push_back(hps[i]);
        pts.push_back(intersect(dq[dq.size()-2], dq.back()));
    }
    // final cleanup: front might be invalidated by back
    while ((int)pts.size() > 1 && outside(dq.front(), pts.back())) {
        pts.pop_back(); dq.pop_back();
    }
    if ((int)dq.size() < 3) return {};
    pts.push_back(intersect(dq.front(), dq.back()));

    return vector<P>(pts.begin(), pts.end());
}

Practical Notes

Bounding box trick: many problems have implicit bounds (coordinates $\le {10}^6$). Add four half-planes forming a large bounding box to ensure the intersection is always bounded -- this simplifies the deque logic and avoids unbounded-region edge cases.

Integer vs. floating point: half-plane intersection almost always requires floating point because intersection points rarely have integer coordinates. Use long double and EPS ~= 1e-9. Double-check with slightly different EPS values if you get WA.

atan2 precision warning. This template sorts by atan2(d.y, d.x), which is convenient and easy to read but loses precision exactly when half-planes are nearly parallel — which is when the algorithm's correctness depends on getting the order right. For integer-coordinate inputs (or any input where you can avoid atan2), prefer a cross-product-based angular comparator: split the plane into upper and lower half-spaces by the sign of d.y (and the sign of d.x when d.y == 0), then compare within each half-space using cross(a.d, b.d). That comparator is exact for integer inputs and stays robust on near-parallel half-planes. The current atan2-based version is fine for most contest inputs but is the first thing to switch out if you hit unexplained WA on near-parallel cases.

Gotchas

Trap	What happens	Fix
Not handling parallel half-planes	Degenerate intersection, crash	Keep tighter of two parallels
Missing final cleanup pass	Wrong polygon -- front vertices become infeasible	Always do front-vs-back check
Unbounded result	Algorithm returns partial/wrong polygon	Add bounding box half-planes
EPS too large or too small	False intersections or missed valid ones	Test with ${10}^{-9}$ and ${10}^{-7}$

Self-Test

Q1. Why must half-planes be sorted by the angle of their direction vector?

Answer

The deque-based algorithm relies on the fact that consecutive half-planes in angle order form a "convex chain." Processing out of order would break the invariant that only the front and back of the deque can become infeasible, making the $O(n)$ deque sweep incorrect.

Q2. What is the "bounding box trick" and why is it important?

Answer

Add four large half-planes (e.g., $x \le 10^6$, $x \ge -10^6$, $y \le 10^6$, $y \ge -10^6$) to guarantee the intersection is bounded. Without this, the result might be an unbounded region (a "wedge" or strip), which the deque algorithm handles poorly -- vertex enumeration fails for unbounded polygons.

Q3. Two half-planes have the same direction angle but different offsets. Which one do you keep?

Answer

Keep the *tighter* (more restrictive) one. Since both have the same direction, they're parallel with the feasible side on the same side. The tighter one's boundary is further into the feasible side, so it dominates -- any point satisfying the tighter constraint also satisfies the looser one.

Q4. The algorithm does a "final cleanup pass." What goes wrong if you skip it?

Answer

The last few half-planes added can make the front of the deque infeasible. Without cleanup, the returned polygon includes vertices outside the true intersection. The final pass pops back-of-deque entries that violate the front constraint, then closes the polygon.

Practice Problems

Problem	What it tests
POJ 3130 -- How I Mathematician Wonder	Polygon kernel existence
POJ 1279 -- Art Gallery	Kernel area
CF 762E -- Radio Stations	Half-plane intersection for feasibility
LA 4992 -- Jungle Outpost	Binary search + HPI

Further Reading

• Geometry Basics -- cross product, line representation
• Convex Hull -- the dual problem (points -> polygon vs. constraints -> polygon)
• Rotating Calipers (or the contest template) -- queries on the resulting convex polygon

---