1054MediumArrayBinary Search

The Line That Halves the Painted Area

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def separate_squares(squares: list[list[int]]) -> float:

Java

public double separateSquares(int[][] squares)

The intended approach

Time O(n * 100) for n squares, that is one pass per halving step.Space O(1).

How much area sits below a height never falls as the height rises: it starts at nothing below everything and finishes at the whole total above everything. So the wanted height can be closed in on by halving, asking at each step whether the area below already reaches half the total. The area below a given height comes square by square. A square finishing below the line contributes all of its area, one starting above it contributes nothing, and one straddling the line contributes its width times how far the line sits above its bottom edge. Since overlaps count once per square, no square ever has to be compared with another. Halve the range from the lowest bottom edge to the highest top edge, keeping the upper half only when the area below falls short. Because the answer need only be right to within a hundred-thousandth, a fixed number of halvings settles it whatever the coordinates, and each one costs a single pass over the squares.

Pythonentry point: separate_squares

def separate_squares(squares):
    total = 0.0
    low = None
    high = None
    for square in squares:
        y = square[1]
        side = square[2]
        total += float(side) * float(side)
        if low is None or y < low:
            low = y
        if high is None or y + side > high:
            high = y + side
    want = total / 2.0
    lo = float(low)
    hi = float(high)
    for _ in range(100):
        mid = (lo + hi) / 2.0
        below = 0.0
        for square in squares:
            y = square[1]
            side = square[2]
            if mid <= y:
                continue
            if mid >= y + side:
                below += float(side) * float(side)
            else:
                below += float(side) * (mid - float(y))
        if below >= want:
            hi = mid
        else:
            lo = mid
    return hi

The obvious version

Work it out exactly instead of closing in. Every bottom and top edge marks a height where the total width of squares crossing the line changes, so between two neighbouring marks the area below grows at a steady rate. Sort the marks, walk the bands between them keeping the area below, and when a band is the one where half is reached, divide the shortfall by that band's width to land on the exact height. Costs a pass over the squares per band rather than per halving step.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_separate_squares(squares):
    total = 0.0
    edges = set()
    for square in squares:
        y = square[1]
        side = square[2]
        total += float(side) * float(side)
        edges.add(y)
        edges.add(y + side)
    want = total / 2.0
    marks = sorted(edges)
    below = 0.0
    for at in range(len(marks) - 1):
        bottom = marks[at]
        if below >= want:
            return float(bottom)
        top = marks[at + 1]
        width = 0.0
        for square in squares:
            y = square[1]
            side = square[2]
            if y <= bottom and y + side >= top:
                width += float(side)
        band = width * float(top - bottom)
        if below + band >= want and width > 0.0:
            return float(bottom) + (want - below) / width
        below += band
    return float(marks[len(marks) - 1])

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in