Find where to cut cake into equal areas

Problem Statement

You are given a set of n rectangles placed side-by-side along the x-axis. Each rectangle i is defined by its width w[i] and height h[i]. All rectangles start at y=0. Because they are placed contiguously, the x-coordinates of the rectangles are [0, w[0]], [w[0], w[0]+w[1]], ..., [sum(w), sum(w)+w[n]].

Your task is to find a vertical line x = k such that the area of the rectangles to the left of the line is exactly half of the total area of all rectangles combined.

Function Signature

def find_cut_line(widths: List[float], heights: List[float]) -> float:

Constraints

• 1 <= n <= 10^5
• 0 < w[i], h[i] <= 10^4
• The result should be accurate to within 10^-6.

Examples

Example 1:

• widths = [2, 2], heights = [1, 3]
• Total area = (2 * 1) + (2 * 3) = 8. Target area = 4.
• The first rectangle has area 2. We need 2 more from the second rectangle. Since the second rectangle has height 3, we need a width of 2 / 3 into it.
• Result: 2 + 0.666667 = 2.666667

Example 2:

• widths = [1, 1], heights = [5, 5]
• Total area = 10. Target area = 5.
• The first rectangle has area 5.
• Result: 1.0

Edge Cases

• n=1: The cut line is simply width / 2.
• All widths/heights equal: The cut line is exactly at total_width / 2.