Practice/Google/Leetcode 3453. Separate Squares I

Leetcode 3453. Separate Squares I

CodingMust

Problem

You are given a collection of axis-aligned squares on a 2D plane. Each square is defined by three values: (x, y, side_length) where (x, y) is the bottom-left corner coordinate and side_length is the length of each side. The square extends from (x, y) to (x + side_length, y + side_length).

When squares overlap, the overlapping regions are counted multiple times (once for each square that covers that region). Your task is to find the smallest y-coordinate of a horizontal line that divides the plane such that the total area of all squares (counting overlaps) above the line equals the total area below the line.

Return the y-coordinate as a floating-point number. If multiple y-values satisfy the condition, return the smallest one.

Requirements

1. Calculate the total weighted area above and below a horizontal line at any given y-coordinate
2. Account for partial squares that are split by the dividing line
3. Count overlapping regions multiple times according to how many squares cover them
4. Find the exact y-coordinate where the areas are balanced
5. Return the result with sufficient precision (at least 6 decimal places)

Constraints

• 1 ≤ squares.length ≤ 1000
• Each square is defined as [x, y, side_length] where all values are integers
• -10^6 ≤ x, y ≤ 10^6
• 1 ≤ side_length ≤ 10^6
• The balance line always exists and is unique

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 equal parts of area 2 each.

Example 2:

Input: squares = [[0, 0, 2], [3, 3, 2]] Output: 2.5 Explanation: First square spans y ∈ [0,2] with area 4, second spans y ∈ [3,5] with area 4. At y=2.5: below we have all of first square (4) + none of second (0) = 4 above we have none of first (0) + all of second (4) = 4

Example 3:

Input: squares = [[0, 0, 4], [1, 1, 2]] Output: 2.0 Explanation: Outer square has area 16, inner square has area 4. They overlap in region [1,3]×[1,3]. The balance line at y=2.0 divides the combined weighted area equally.