Lowest Horizontal Cut That Splits Square Cakes Into Equal Total Areas

Several square cakes sit on a table, each with its sides parallel to the table's edges. You make one long horizontal cut across the whole table, along a line y = h. Every cake crossed by the line is split into a part below the line and a part above it; a cake entirely on one side stays whole on that side. Find where to cut so that the total area of cake below the line equals the total area of cake above it.

Model the table as the plane seen from above. Each cake is a square given by its bottom-left corner and its side length.

Function Signature

def balanced_cut_height(squares: list[list[int]]) -> list[int]:

Rules

• squares[i] = [x, y, side] describes the square with corners (x, y) and (x + side, y + side).
• Areas are added up cake by cake: if two squares overlap, the overlapping region counts once for each square.
• For a line y = h, the area below the line is the sum over all squares of the part of each square with y-coordinate less than h; the area above is defined symmetrically.
• Several heights can balance the areas (for example, anywhere in an empty gap between cakes). Return the smallest such h.
• Return h exactly as a reduced fraction [numerator, denominator] with denominator > 0 and gcd(numerator, denominator) = 1. An integer height h is returned as [h, 1].

Constraints

• 1 <= len(squares) <= 10^4
• 0 <= x, y <= 10^6
• 1 <= side <= 10^3
• The numerator and denominator of the answer are below 2^53.

Examples

Example 1

• Input: squares = [[0, 0, 2], [1, 1, 1]]
• Output: [7, 6]
• Explanation: The total area is 4 + 1 = 5, so each side needs 2.5. Up to h = 1 only the first square is cut, giving area 2 below. Between 1 and 2 both squares are cut, adding 3 per unit of height, so the balance is reached at h = 1 + 0.5 / 3 = 7/6.

Example 2

• Input: squares = [[0, 0, 1], [2, 2, 1]]
• Output: [1, 1]
• Explanation: Any line between y = 1 and y = 2 leaves one square on each side. The smallest such height is 1.

Example 3

• Input: squares = [[0, 0, 1], [0, 0, 1], [3, 1, 2]]
• Output: [3, 2]
• Explanation: The first two squares are identical and both count. The total area is 1 + 1 + 4 = 6. At h = 1 the area below is 2; above y = 1 only the third square adds area, 2 per unit of height, so the remaining 1 is reached at h = 1.5.

Equal-Area Horizontal Cake Cut

Hints

1. Only the y-coordinate and side of each square matter. How does the area below the line change as h moves up by one unit?
2. Between two consecutive bottom/top edges, the area below grows linearly at a rate equal to the total side length of the squares the line currently crosses.
3. Sweep the sorted edge heights, find the first segment where the area below reaches half the total, and solve the linear equation there. Doubling every area keeps all arithmetic in integers.

Approach

Let A be the total area (sum of side^2). The area below the line, f(h), is continuous and non-decreasing, and between two consecutive edge heights it is linear with slope equal to the sum of the sides of the squares that straddle the line. Record +side at each bottom edge y and -side at each top edge y + side, sort the distinct heights, and sweep upward keeping the current slope (rate) and the area accumulated so far. To avoid the fraction A/2, keep every area doubled: the target is A and each segment [p, q] contributes 2 * rate * (q - p). In the first segment where the doubled area reaches the target, the rate is positive and the balance point is h = p + (A - below) / (2 * rate) = (2 * rate * p + A - below) / (2 * rate); reduce it by the gcd. Because the sweep stops at the first segment that reaches the target, the h it returns is the smallest balancing height; in an empty gap the rate is zero, so a balance reached at the top of a band is returned as that band's upper edge rather than any point further up the gap.

• Time complexity: O(n log n)
• Space complexity: O(n)