Skip to content

Splitting Cakes

Level: L3-L5 Topics: Binary Search, Geometry, Computational Geometry

Problem Statement

You have several square cakes placed on a table (a 2D plane). Each cake is defined by its bottom-left corner coordinates and its side length, with sides parallel to the axes.

Find the exact y-coordinate of a horizontal line that splits the total cake area into two equal halves: the total area above the line equals the total area below the line.

Background & Constraints

  • Each cake is an axis-aligned square defined by (x, y, side_length) where (x, y) is the bottom-left corner.
  • Cakes may overlap. Overlapping regions should be counted only once in the total area (union of squares).
  • The cutting line is horizontal (constant y-value).
  • The line may pass through cakes, splitting them into top and bottom portions.
  • A solution always exists (assuming total area > 0).
  • The answer should be exact or within a specified precision (e.g., 10^-6).

Examples

Example 1 — Single cake:

Cake: bottom-left (0, 0), side = 4
Total area: 16
Cut at y = 2 → bottom area = 8, top area = 8
Answer: y = 2.0

Example 2 — Two non-overlapping cakes:

Cake A: bottom-left (0, 0), side = 2   (area 4)
Cake B: bottom-left (5, 3), side = 2   (area 4)
Total area: 8

A horizontal line at y = 2 gives:
- Below: all of Cake A (4) + none of Cake B (0) = 4
- Above: none of Cake A (0) + all of Cake B (4) = 4
Answer: y = 2.0

Example 3 — Stacked cakes:

Cake A: bottom-left (0, 0), side = 4   (area 16)
Cake B: bottom-left (0, 4), side = 4   (area 16)
Total area: 32

Cut at y = 4 → bottom = 16, top = 16
Answer: y = 4.0

Hints & Common Pitfalls

  • Binary search on y-coordinate: The area below a horizontal line at height y is a monotonically non-decreasing function of y. This makes it suitable for binary search.

  • Computing area below a line: For each cake, the area below the line at height y is:

    • 0 if y <= cake.bottom
    • side * (y - cake.bottom) if cake.bottom < y < cake.top
    • side * side (full area) if y >= cake.top

  • Handling overlaps: If cakes overlap, naive summation overcounts. You need to compute the union area below the line. One approach: for each y-value during binary search, compute the union of horizontal cross-sections using interval merging along the x-axis.

  • Precision: Binary search on a continuous domain converges quickly. After ~50 iterations with halving, you achieve precision around 10^-15 relative to the initial range.

  • Common mistake: Forgetting about overlapping cakes. If the problem states cakes do not overlap, the solution is simpler (just sum individual contributions).

Follow-Up Questions

  1. Prove convergence: Why does binary search converge for this problem? Formally, show that the "area below line at y" function is continuous and monotonically non-decreasing in y.

  2. Three equal portions: Find two horizontal lines y1 < y2 that divide the total area into three equal parts. How does this extend the binary search approach? Can you nest two binary searches, or is there a more efficient method?

  3. Vertical cut instead: What if you need to find a vertical line that splits the area in half? Does the same approach work? What about an arbitrary-angle line?

  4. Weighted split: Instead of equal halves, split into a ratio of p:(1-p). Does this change the algorithm in any fundamental way?