1class Solution {
2    // The list of squares, where each square is represented as [x, y, sideLength].
3    private int[][] squares;
4    // The total area of all squares combined.
5    private double totalArea;
6
7    /**
8     * Checks whether a horizontal line at height {@code lineY} splits the squares
9     * such that the area below the line is at least half of the total area.
10     *
11     * @param lineY the candidate y-coordinate of the horizontal line
12     * @return true if the area below {@code lineY} is at least half the total area
13     */
14    private boolean check(double lineY) {
15        double areaBelow = 0.0;
16        for (int[] square : squares) {
17            int bottomY = square[1];
18            int sideLength = square[2];
19            // Only squares whose bottom edge is below the line contribute area.
20            if (bottomY < lineY) {
21                // The covered height is capped by the square's side length.
22                areaBelow += (double) sideLength * Math.min(lineY - bottomY, sideLength);
23            }
24        }
25        return areaBelow >= totalArea / 2.0;
26    }
27
28    /**
29     * Finds the minimum y-coordinate of a horizontal line that divides the
30     * total area of all squares into two equal halves.
31     *
32     * @param squares the array of squares, each as [x, y, sideLength]
33     * @return the y-coordinate of the dividing horizontal line
34     */
35    public double separateSquares(int[][] squares) {
36        this.squares = squares;
37        totalArea = 0.0;
38
39        // Binary search bounds on the y-coordinate of the dividing line.
40        double low = 0.0;
41        double high = 0.0;
42        for (int[] square : squares) {
43            // Accumulate the area of each square (side length squared).
44            totalArea += (double) square[2] * square[2];
45            // The upper bound is the highest top edge among all squares.
46            high = Math.max(high, square[1] + square[2]);
47        }
48
49        // Binary search for the smallest line height satisfying the area condition.
50        double eps = 1e-5;
51        while (high - low > eps) {
52            double mid = (low + high) / 2.0;
53            if (check(mid)) {
54                high = mid;
55            } else {
56                low = mid;
57            }
58        }
59        return high;
60    }
61}
62

1class Solution {
2public:
3    // Pointer to the input squares for use inside the helper function
4    vector<vector<int>>* squares;
5    // Total area of all squares combined
6    double totalArea;
7
8    // Checks whether the horizontal line y = lineY splits the squares such that
9    // the area below the line is at least half of the total area
10    bool check(double lineY) {
11        double areaBelow = 0.0;
12        for (const auto& square : *squares) {
13            int bottomY = square[1];      // y-coordinate of the square's bottom edge
14            int sideLength = square[2];   // side length of the square
15
16            // Only squares whose bottom edge lies below the line contribute area
17            if (bottomY < lineY) {
18                // The vertical overlap is capped by the square's side length,
19                // multiplied by the width (also the side length) to get the area
20                areaBelow += (double) sideLength * min(lineY - bottomY, (double) sideLength);
21            }
22        }
23        // True if the area below the line reaches at least half the total area
24        return areaBelow >= totalArea / 2.0;
25    }
26
27    double separateSquares(vector<vector<int>>& squares) {
28        this->squares = &squares;
29        totalArea = 0.0;
30
31        double low = 0.0;   // Lower bound of the search interval for the dividing line
32        double high = 0.0;  // Upper bound of the search interval for the dividing line
33
34        // Compute the total area and find the highest top edge to bound the search
35        for (const auto& square : squares) {
36            totalArea += (double) square[2] * square[2];      // accumulate area (side^2)
37            high = max(high, (double) square[1] + square[2]); // bottom + side = top edge
38        }
39
40        const double eps = 1e-5; // Precision threshold for binary search
41
42        // Binary search for the smallest line position that satisfies the half-area condition
43        while (high - low > eps) {
44            double mid = (low + high) / 2.0;
45            if (check(mid)) {
46                // Line is high enough (or too high); try lowering it
47                high = mid;
48            } else {
49                // Not enough area below; raise the line
50                low = mid;
51            }
52        }
53
54        // Either bound is acceptable within the epsilon tolerance
55        return high;
56    }
57};
58

1/**
2 * Finds a horizontal line y = result such that the total area of squares
3 * below the line equals the total area of squares above the line.
4 *
5 * @param squares - Each square is [x, y, sideLength], where (x, y) is the
6 *                  bottom-left corner and sideLength is the side length.
7 * @returns The y-coordinate of the dividing horizontal line.
8 */
9function separateSquares(squares: number[][]): number {
10    /**
11     * Checks whether the area of all squares lying below the line y = lineY
12     * is at least half of the total area.
13     *
14     * @param lineY - The candidate y-coordinate of the horizontal line.
15     * @returns True if the area below the line is >= half of the total area.
16     */
17    const check = (lineY: number): boolean => {
18        let areaBelow = 0;
19        for (const [, bottomY, sideLength] of squares) {
20            // Only squares whose bottom edge is below the line contribute.
21            if (bottomY < lineY) {
22                // The covered vertical height is capped by the square's side length.
23                const coveredHeight = Math.min(lineY - bottomY, sideLength);
24                areaBelow += sideLength * coveredHeight;
25            }
26        }
27        return areaBelow >= totalArea / 2;
28    };
29
30    // Total area of all squares and the binary search boundaries.
31    let totalArea = 0;
32    let low = 0;
33    let high = 0;
34    for (const [, bottomY, sideLength] of squares) {
35        totalArea += sideLength * sideLength;
36        // The highest possible line is the top edge of the topmost square.
37        high = Math.max(high, bottomY + sideLength);
38    }
39
40    // Binary search on the answer with a precision tolerance.
41    const eps = 1e-5;
42    while (high - low > eps) {
43        const mid = (low + high) / 2;
44        if (check(mid)) {
45            // Area below is already >= half, so move the line downward.
46            high = mid;
47        } else {
48            // Area below is too small, so move the line upward.
49            low = mid;
50        }
51    }
52
53    return high;
54}
55