Find a Horizontal Cut That Bisects Rectangle Area

Problem Statement

You are given a list of axis-aligned rectangles. Each rectangle is represented by a tuple of four integers [x, y, w, h], where (x, y) denotes the coordinates of the bottom-left corner, w is its width, and h is its height (w > 0, h > 0).

The given rectangles are pairwise interior-disjoint (i.e., they do not overlap, though they may share edges or vertices).

Your task is to find the y-coordinate of a horizontal line Y = c such that the total area of the rectangles lying below this line is exactly half of the combined total area of all rectangles.

For a rectangle [x, y, w, h]:

• If c = y + h, the area below c is w * h.
• If y < c < y + h, the area below c is w * (c - y).

Return the value c as a floating-point number. Answers within an absolute or relative error of 1e-5 will be accepted.

Function Signature

def find_bisecting_line(rectangles: list[list[int]]) -> float:
    pass

Constraints

• 1 <= len(rectangles) <= 200,000
• 0 <= x, y <= 10^9
• 1 <= w, h <= 10^9
• All input values are integers.
• Rectangles do not overlap in their interiors.

Examples

Example 1

Input: rectangles = [[0, 0, 4, 4]]
Output: 2.0
Explanation:
The total area is 4 * 4 = 16. Half the area is 8.
The horizontal line Y = 2 cuts the rectangle into two equal halves of height 2 and area 8.

Example 2

Input: rectangles = [[0, 0, 2, 2], [5, 0, 2, 6]]
Output: 2.75
Explanation:
- Area of rectangle 1: 2 * 2 = 4
- Area of rectangle 2: 2 * 6 = 12
- Total area: 16. Target area below line: 8.
At Y = 2, the area below the line is (2 * 2) + (2 * 2) = 8. Wait:
- Below Y = 2: Rectangle 1 is completely below (area 4), Rectangle 2 contributes 2 * 2 = 4. Total = 8.
Thus, Y = 2.0 is the exact cut.

Edge Cases

• Disjoint heights: Rectangles with large gaps in the y-dimension. Any y-value within the gap may yield the same area; any valid value in that gap is acceptable.
• Extreme numbers: Coordinate values up to 10^9 and rectangle count up to 200,000 mean total area can reach 2 * 10^23. Be cautious of 64-bit integer overflows in languages like C++ or Java.