Show problems as
Classic problem #3453MediumArrayBinary Search

Separate Squares I

Real-world version: The Line That Halves the Painted Area
Tracked in this browser only
Read Separate Squares I on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Squares are given as squares, where squares[i] = [x, y, side] places a square with its bottom-left corner at (x, y) and its sides of length side parallel to the axes. Squares may overlap, and an overlapping patch counts once for every square covering it.

Find the smallest height h such that the horizontal line at that height leaves as much square area below it as above it, and return h.

An answer within 10^-5 of the true one is accepted.

Examples

Example 1

Input
squares = [[0, 0, 2], [0, 2, 2]]
Output
2.0

Two squares of area four stand one on top of the other, so the line has to leave four below it, which is exactly the join between them.

Example 2

Input
squares = [[0, 0, 2], [0, 1, 1]]
Output
1.1666666666666667

The areas are four and one, so the line must leave two and a half below it. Above height one both squares straddle the line, and their widths of two and one together raise the area below by three for every unit of height, so half is reached a sixth of the way up.

Example 3

Input
squares = [[0, 0, 1], [0, 3, 1]]
Output
1.0

Each square has area one, so the line must leave one below it. The lower square finishes at height one, and nothing else is painted until height three, so one is the smallest height that works.

Constraints

  • 1 <= squares.length <= 5 * 10^4
  • squares[i].length == 3
  • 0 <= squares[i][0] <= 10^9
  • 0 <= squares[i][1] <= 10^9
  • 1 <= squares[i][2] <= 10^9
  • The squares' total area does not exceed 10^12.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def separate_squares(squares: list[list[int]]) -> float:
Java
public double separateSquares(int[][] squares)

More on the same topics