Find the horizontal line that splits the total area covered by axis-aligned squares into two equal halves.
Problem
You are given a list of axis-aligned squares on a 2D plane. Each square is represented by its bottom-left corner and side length.
Choose a horizontal line such that the total area of all square regions lying strictly below the line is equal to the total area lying strictly above the line.
Return the value of .
If multiple values are possible, return any one of them. The answer should be accurate to within a small floating-point tolerance.
Notes
- Squares may overlap.
- Overlapping regions contribute area multiple times, once for each square.
- The line is horizontal, so only the -coordinates matter for the split.
Input Format
- An array of squares.
- Each square is described by three values:
x,y,side, where(x, y)is the bottom-left corner andsideis the side length.
Although x is provided, the splitting line is horizontal, so the answer depends only on the vertical placement and sizes of the squares.
Output Format
- Return a floating-point number
hrepresenting the y-coordinate of the horizontal split line.
Constraints
- Each square has positive side length.
- The number of squares is at least 1.
- Area calculations may require floating-point precision.
- Squares may overlap and can have arbitrary coordinates within typical integer limits.
Example 1
Input
squares = [[0,0,2],[1,1,2]]
Output
1.500000
Explanation
The total area is 8. A horizontal line at y = 1.5 splits the combined area into 4 below and 4 above, counting overlap separately for each square.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.