The Geometric Eclipse
The One Thing That Matters
Lesson 1 set up the geometry: lines go on a stack, the lower envelope is the answer, and some lines get eclipsed when a new one arrives. But we hand-waved the actual pop condition.
Now we nail it down. This is the math at the heart of the Convex Hull Trick, and once you understand it, the rest is bookkeeping.
Two Lines, One Intersection
Start simple. Two lines:
They intersect where f_A(x) = f_B(x):
That's it. The intersection x-coordinate is (c_B - c_A) / (m_A - m_B). We'll call this x(A, B).
To the left of this point, whichever line has the steeper slope wins (gives a smaller y for the minimum envelope). To the right, the shallower line wins.
Three Lines, One Victim
Now the real question. You have three lines in the envelope, ordered by decreasing slope:
- Line A (steepest) — deepest in the stack
- Line B (medium) — top of the stack
- Line C (shallowest) — the new line being added
Line B currently sits between A and C on the envelope. It wins in the interval between x(A, B) and x(B, C). But when we add line C, we need to ask: does B still win ANYWHERE?
Line B is eclipsed if line C takes over before B even starts. In other words, B is eclipsed if:
Think about what this means geometrically. Line C intersects line A at the same point (or earlier) where B intersects A. So C is already lower than B at the point where B was supposed to take over from A. Line B never gets a chance. It's squeezed between A and C, above both of them at every point.
A Concrete Example
Let's work through real numbers. Three lines:
- Line A: y = 5x + 1 (steep, entered first)
- Line B: y = 3x + 4 (medium, entered second)
- Line C: y = x + 8 (shallow, entering now)
First, where do A and B intersect?
At x = 1.5, both give y = 8.5. For x < 1.5, A wins. For x > 1.5, B wins.
Now, where do A and C intersect?
At x = 1.75, both give y = 9.75.
Here's the problem for B. Line C intersects A at x = 1.75, which is AFTER x = 1.5 where B intersects A. So B does get a tiny window: from x = 1.5 to x = 1.75. B isn't fully eclipsed.
Let's change the numbers. Suppose:
- Line A: y = 5x + 1
- Line B: y = 3x + 6
- Line C: y = x + 8
Now:
x(A, C) = 1.75 < x(A, B) = 2.5. Line C intersects A at x = 1.75, but B doesn't take over from A until x = 2.5. At x = 1.75, C is already below A, and it's below B too (check: B gives 3(1.75) + 6 = 11.25, C gives 1.75 + 8 = 9.75). So by the time B would have started winning, C is already winning instead.
B is eclipsed. Pop it.
After popping B, the envelope is just A and C. They intersect at x = 1.75. A wins for x < 1.75, C wins for x > 1.75. Clean.
The Structural Invariant
Here's another way to see the pop condition. The envelope maintains an invariant: the intersection x-coordinates of consecutive lines must be strictly increasing.
If the envelope contains lines L1, L2, L3 (in order of decreasing slope), then we need:
Each line's "active interval" starts where it takes over from its predecessor and ends where it hands off to its successor. If the intersection points aren't increasing, some line has a negative-length interval. That line is eclipsed — it has no active zone.
When you add a new line C, you compute x(B, C) where B is the top of the stack. If x(B, C) <= x(A, B) (where A is second-from-top), the invariant breaks. Pop B and repeat.
This is exactly analogous to the monotonic stack invariant. In NGE, the stack values were decreasing. Here, the intersection x-coordinates are increasing. A violation means something needs to be popped.
Integer Arithmetic: Avoid the Division
The intersection formula involves division: x = (c_B - c_A) / (m_A - m_B). Division means floating point, and floating point means precision errors that will bite you on competitive programming judges.
The fix: cross-multiply.
We want to check if x(A, C) <= x(A, B). That's:
Cross-multiplying (and being careful about the sign of the denominators — since slopes are decreasing, m_A - m_C > 0 and m_A - m_B > 0, so the inequality direction is preserved):
Or equivalently, rearranging to match common implementations:
Both sides are integers if the slopes and intercepts are integers. No division, no floating point. If the products might overflow 64-bit integers (slopes and intercepts up to 10^9), use __int128.
bool eclipsed(Line a, Line b, Line c) {
return (__int128)(a.c - c.c) * (b.m - a.m)
<= (__int128)(a.c - b.c) * (c.m - a.m);
}
This is the entire pop condition in one line. Memorize it, or better yet, derive it from scratch a few times until it's second nature.
A DP Problem: Machine Processing
Let's apply this to a concrete DP problem. This is a simplified version of problems like APIO Commando or USACO Barn Painting.
Problem: You have N machines numbered 0 to N-1. Each machine i has a processing rate a[i] (decreasing) and a batch size b[i] (increasing). The cost of assigning batch i to be processed starting from machine j is dp[j] + a[j] * b[i], where dp[j] is the cost accumulated up to machine j.
You want to find the minimum cost to process all batches. The recurrence:
Rewrite: each candidate j defines a line with slope a[j] and intercept dp[j]. We query at x = b[i].
Since a[j] is decreasing, lines arrive in decreasing slope order. Since b[i] is increasing, queries come in increasing x order. Both conditions hold — we get the full O(N) algorithm with a deque and a pointer.
The algorithm:
- Start with
dp[0] = 0and add line (slope = a[0], intercept = 0) to the hull. - For each i from 1 to N-1:
- Query: advance the front pointer while the next line is better at x = b[i]. The front gives
dp[i]. - Insert: create line (slope = a[i], intercept = dp[i]). Pop eclipsed lines from the back. Push.
- Answer is
dp[N-1].
Notice that we're building the envelope and querying it simultaneously. As we compute each dp[i], we immediately turn it into a new candidate line for future states. This interleaving is typical of CHT-optimized DP.
Walking Through the DP
Input: N = 4, a = [7, 5, 3, 1], b = [1, 3, 5, 8]
i = 0: dp[0] = 0. Hull: {L0: y = 7x + 0}.
i = 1: Query at x = b[1] = 3. Only one line: dp[1] = 7*3 + 0 = 21. Add L1: y = 5x + 21. Check eclipse: only 2 lines, nothing to eclipse. Hull: {L0, L1}.
i = 2: Query at x = b[2] = 5. Front is L0: 75 + 0 = 35. Next is L1: 55 + 21 = 46. L0 is better. dp[2] = 35. Add L2: y = 3x + 35. Eclipse check: is L1 eclipsed by L0 and L2? x(L0, L1) = (21 - 0)/(7 - 5) = 10.5. x(L0, L2) = (35 - 0)/(7 - 3) = 8.75. Since 8.75 < 10.5, yes — L1 is eclipsed. Pop L1. Hull: {L0, L2}.
i = 3: Query at x = b[3] = 8. Front is L0: 78 + 0 = 56. Next is L2: 38 + 35 = 59. L0 is better. dp[3] = 56. Add L3: y = x + 56. Eclipse check: is L2 eclipsed by L0 and L3? x(L0, L2) = 8.75. x(L0, L3) = (56 - 0)/(7 - 1) = 9.33. Since 9.33 > 8.75, L2 is NOT eclipsed. Hull: {L0, L2, L3}.
Answer: dp[3] = 56.
Notice how at i = 2, line L1 got eclipsed even though it was a valid part of the envelope before L2 arrived. That's the stack in action — the most recent line is the first to go.
The Pop Loop, One More Time
Let's zoom in on the pop loop, because getting it right is everything.
void addLine(deque<Line>& hull, Line nw) {
while (hull.size() >= 2) {
Line& a = hull[hull.size() - 2]; // second from top
Line& b = hull[hull.size() - 1]; // top
if (eclipsed(a, b, nw))
hull.pop_back();
else
break;
}
hull.push_back(nw);
}
This mirrors the monotonic stack pop loop perfectly:
Same structure. Different condition. The monotonic stack checks a simple value comparison. The CHT checks a geometric eclipse condition. But the amortized O(N) argument is identical: each line is pushed once and popped at most once.
Try It
The starter code implements the machine processing DP problem. You need to fill in the eclipsed function — that's the only missing piece. Everything else is wired up: the deque, the front-pointer query, and the back-popping insert.
Input format: Line 1: N Line 2: a[0] a[1] ... a[N-1] (decreasing processing rates) Line 3: b[0] b[1] ... b[N-1] (increasing batch sizes)
Output: The minimum cost dp[N-1].
Example:
Expected output: 56
Once you get it working, try tracing through the hull at each step. Verify that the intersection x-coordinates of consecutive lines are always increasing. That's the invariant that makes everything work.