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 ```python 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`.