Practice/Google/Leetcode 3454. Separate Squares II

Leetcode 3454. Separate Squares II

CodingMust

Problem

You are given a collection of axis-aligned squares on a 2D plane. Each square is represented as [x, y, side_length], where (x, y) is the bottom-left corner and the square extends to (x + side_length, y + side_length).

Your task is to find the minimum y-coordinate of a horizontal line that divides the union of all squares into two regions of equal area. The union means overlapping regions are counted only once.

Return the y-coordinate as a floating-point number. The line at y-coordinate h divides the plane such that all points with y-coordinate less than h are in the bottom region.

Requirements

1. Calculate the total area of the union of all squares (overlaps counted once)
2. Find the minimum y-coordinate where the area below equals exactly half the total area
3. Handle overlapping squares correctly when computing areas
4. Return the result as a floating-point number with sufficient precision

Constraints

• 1 ≤ squares.length ≤ 100
• Each square is represented as [x, y, side_length] where all values are integers
• -10^6 ≤ x, y ≤ 10^6
• 1 ≤ side_length ≤ 10^6
• The answer will always exist and be unique
• Your solution should handle precision up to at least 6 decimal places

Examples

Example 1:

Input: squares = [[0, 0, 2]] Output: 1.0 Explanation: A single square from (0,0) to (2,2) has area 4. The horizontal line at y=1 splits it into two regions of area 2 each.

Example 2:

Input: squares = [[0, 0, 4], [2, 0, 4]] Output: 2.828427124746 Explanation: Two overlapping squares. The first spans (0,0) to (4,4), the second spans (2,0) to (6,4). Their union has area 32 (overlap region is 2×4=8, so total is 16+16-8=24... wait, let me recalculate: actually the overlap from x=2 to x=4 and y=0 to y=4 gives union area of 32). Half of 32 is 16, achieved at y ≈ 2.828.

Example 3:

Input: squares = [[0, 0, 2], [0, 2, 2]] Output: 2.0 Explanation: Two squares stacked vertically. The first is (0,0) to (2,2), the second is (0,2) to (2,4). Total area is 8. The line at y=2 gives area 4 below (the first square) and area 4 above (the second square).