目标
给你一个二维整数数组 squares ，其中 squares[i] = [xi, yi, li] 表示一个与 x 轴平行的正方形的左下角坐标和正方形的边长。
找到一个最小的 y 坐标，它对应一条水平线，该线需要满足它以上正方形的总面积 等于 该线以下正方形的总面积。
答案如果与实际答案的误差在 10^-5 以内，将视为正确答案。
注意：正方形 可能会 重叠。重叠区域应该被 多次计数 。
示例 1：
输入： squares = [[0,0,1],[2,2,1]]
输出： 1.00000
解释：
任何在 y = 1 和 y = 2 之间的水平线都会有 1 平方单位的面积在其上方，1 平方单位的面积在其下方。最小的 y 坐标是 1。示例 2：
输入： squares = [[0,0,2],[1,1,1]]
输出： 1.16667
解释：
面积如下：
线下的面积：7/6 * 2 (红色) + 1/6 (蓝色) = 15/6 = 2.5。
线上的面积：5/6 * 2 (红色) + 5/6 (蓝色) = 15/6 = 2.5。
由于线以上和线以下的面积相等，输出为 7/6 = 1.16667。说明：
- 1 <= squares.length <= 5 * 10^4
- squares[i] = [xi, yi, li]
- squares[i].length == 3
- 0 <= xi, yi <= 10^9
- 1 <= li <= 10^9
- 所有正方形的总面积不超过 10^12。
思路
二维平面内有一些正方形，squares[i] = [xi, yi, li] 表示正方形坐下顶点坐标为 (xi, yi)，边长为 li。找到最小的 y 水平线，使得这些正方形在水平线上方的面积等于下方的面积，重叠部分的面积应被重复计算。
二分答案，计算上方与下方的面积。
代码
/**
* @date 2026-01-13 9:08
*/
public class SeparateSquares3453 {
public double separateSquares(int[][] squares) {
double l = 0.0, r = 1000000000.0;
double m = l + (r - l) / 2;
while (l <= r) {
if (check(squares, m)) {
r = m - 0.00001;
} else {
l = m + 0.00001;
}
m = l + (r - l) / 2;
}
return l;
}
private boolean check(int[][] squares, double m) {
double upperSum = 0.0, lowerSum = 0.0;
for (int[] square : squares) {
int y = square[1], l = square[2];
if (y + l <= m) {
lowerSum += (double) l * l;
} else if (y >= m) {
upperSum += (double) l * l;
} else {
upperSum += (double) l * (y + l - m);
lowerSum += (double) l * (m - y);
}
}
return upperSum <= lowerSum;
}
}
性能
