LeetCode 3453: Separate Squares I (Binary Search on Horizontal Cut)
LeetCode 3453Binary SearchGeometryToday we solve LeetCode 3453 - Separate Squares I.
Source: https://leetcode.com/problems/separate-squares-i/
English
Problem Summary
Each square is given as [x, y, l] (bottom-left corner and side length). We need the minimum horizontal line Y such that total area above the line equals total area below the line. Overlaps are counted independently per square.
Key Insight
Define below(Y) as total area of all square parts with vertical coordinate <= Y. For one square:
- Y <= y: contributes 0
- Y >= y + l: contributes l*l
- otherwise: contributes l * (Y - y)
So below(Y) is monotonic increasing. We binary-search the smallest Y where below(Y) >= total/2.
Algorithm
1) Compute total = sum(l*l), lo = min(y), hi = max(y+l).
2) Target area is total / 2.
3) Binary search on [lo, hi] (about 60 iterations for precision).
4) If below(mid) >= target, move hi = mid, else lo = mid.
5) Return hi.
Complexity Analysis
Each feasibility check scans all squares once.
Time: O(n * I), where I=60 iterations.
Space: O(1).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public double separateSquares(int[][] squares) {
double total = 0.0;
double lo = Double.POSITIVE_INFINITY;
double hi = Double.NEGATIVE_INFINITY;
for (int[] s : squares) {
double y = s[1], l = s[2];
total += l * l;
lo = Math.min(lo, y);
hi = Math.max(hi, y + l);
}
double target = total / 2.0;
for (int iter = 0; iter < 60; iter++) {
double mid = (lo + hi) / 2.0;
if (areaBelow(squares, mid) >= target) {
hi = mid;
} else {
lo = mid;
}
}
return hi;
}
private double areaBelow(int[][] squares, double yLine) {
double sum = 0.0;
for (int[] s : squares) {
double y = s[1], l = s[2];
if (yLine <= y) continue;
if (yLine >= y + l) sum += l * l;
else sum += l * (yLine - y);
}
return sum;
}
}func separateSquares(squares [][]int) float64 {
total := 0.0
lo := 1e18
hi := -1e18
for _, s := range squares {
y := float64(s[1])
l := float64(s[2])
total += l * l
if y < lo {
lo = y
}
if y+l > hi {
hi = y + l
}
}
target := total / 2.0
for iter := 0; iter < 60; iter++ {
mid := (lo + hi) / 2.0
if areaBelow(squares, mid) >= target {
hi = mid
} else {
lo = mid
}
}
return hi
}
func areaBelow(squares [][]int, yLine float64) float64 {
sum := 0.0
for _, s := range squares {
y := float64(s[1])
l := float64(s[2])
if yLine <= y {
continue
}
if yLine >= y+l {
sum += l * l
} else {
sum += l * (yLine - y)
}
}
return sum
}class Solution {
public:
double separateSquares(vector<vector<int>>& squares) {
double total = 0.0;
double lo = 1e18, hi = -1e18;
for (auto& s : squares) {
double y = s[1], l = s[2];
total += l * l;
lo = min(lo, y);
hi = max(hi, y + l);
}
double target = total / 2.0;
for (int iter = 0; iter < 60; ++iter) {
double mid = (lo + hi) / 2.0;
if (areaBelow(squares, mid) >= target) hi = mid;
else lo = mid;
}
return hi;
}
private:
double areaBelow(vector<vector<int>>& squares, double yLine) {
double sum = 0.0;
for (auto& s : squares) {
double y = s[1], l = s[2];
if (yLine <= y) continue;
if (yLine >= y + l) sum += l * l;
else sum += l * (yLine - y);
}
return sum;
}
};class Solution:
def separateSquares(self, squares: List[List[int]]) -> float:
total = 0.0
lo = float("inf")
hi = float("-inf")
for _, y, l in squares:
total += l * l
lo = min(lo, y)
hi = max(hi, y + l)
target = total / 2.0
def area_below(y_line: float) -> float:
s = 0.0
for _, y, l in squares:
if y_line <= y:
continue
if y_line >= y + l:
s += l * l
else:
s += l * (y_line - y)
return s
for _ in range(60):
mid = (lo + hi) / 2.0
if area_below(mid) >= target:
hi = mid
else:
lo = mid
return hivar separateSquares = function(squares) {
let total = 0;
let lo = Infinity;
let hi = -Infinity;
for (const [x, y, l] of squares) {
total += l * l;
lo = Math.min(lo, y);
hi = Math.max(hi, y + l);
}
const target = total / 2;
const areaBelow = (yLine) => {
let sum = 0;
for (const [x, y, l] of squares) {
if (yLine <= y) continue;
if (yLine >= y + l) sum += l * l;
else sum += l * (yLine - y);
}
return sum;
};
for (let iter = 0; iter < 60; iter++) {
const mid = (lo + hi) / 2;
if (areaBelow(mid) >= target) hi = mid;
else lo = mid;
}
return hi;
};中文
题目概述
每个正方形由 [x, y, l] 表示（左下角坐标 + 边长）。要求找到最小的水平线 Y，使得该线以上面积与以下面积相等。重叠区域按每个正方形独立计入。
核心思路
定义 below(Y) 为所有正方形在 Y 以下部分面积之和。对单个正方形：
- Y <= y：贡献 0
- Y >= y + l：贡献 l*l
- 中间情况：贡献 l * (Y - y)
可见 below(Y) 随 Y 单调不减，因此可以二分查找最小满足 below(Y) >= total/2 的 Y。
算法步骤
1）计算总面积 total = Σ(l*l)，并确定搜索区间 [min(y), max(y+l)]。
2）目标是 target = total / 2。
3）在区间上做约 60 次二分。
4）若 below(mid) >= target，说明可行，收缩右边界；否则收缩左边界。
5）最终返回右边界（或左边界，二者已足够接近）。
复杂度分析
每次判定扫描一次所有正方形。
时间复杂度：O(n * I)，I=60。
空间复杂度：O(1)。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public double separateSquares(int[][] squares) {
double total = 0.0;
double lo = Double.POSITIVE_INFINITY;
double hi = Double.NEGATIVE_INFINITY;
for (int[] s : squares) {
double y = s[1], l = s[2];
total += l * l;
lo = Math.min(lo, y);
hi = Math.max(hi, y + l);
}
double target = total / 2.0;
for (int iter = 0; iter < 60; iter++) {
double mid = (lo + hi) / 2.0;
if (areaBelow(squares, mid) >= target) {
hi = mid;
} else {
lo = mid;
}
}
return hi;
}
private double areaBelow(int[][] squares, double yLine) {
double sum = 0.0;
for (int[] s : squares) {
double y = s[1], l = s[2];
if (yLine <= y) continue;
if (yLine >= y + l) sum += l * l;
else sum += l * (yLine - y);
}
return sum;
}
}func separateSquares(squares [][]int) float64 {
total := 0.0
lo := 1e18
hi := -1e18
for _, s := range squares {
y := float64(s[1])
l := float64(s[2])
total += l * l
if y < lo {
lo = y
}
if y+l > hi {
hi = y + l
}
}
target := total / 2.0
for iter := 0; iter < 60; iter++ {
mid := (lo + hi) / 2.0
if areaBelow(squares, mid) >= target {
hi = mid
} else {
lo = mid
}
}
return hi
}
func areaBelow(squares [][]int, yLine float64) float64 {
sum := 0.0
for _, s := range squares {
y := float64(s[1])
l := float64(s[2])
if yLine <= y {
continue
}
if yLine >= y+l {
sum += l * l
} else {
sum += l * (yLine - y)
}
}
return sum
}class Solution {
public:
double separateSquares(vector<vector<int>>& squares) {
double total = 0.0;
double lo = 1e18, hi = -1e18;
for (auto& s : squares) {
double y = s[1], l = s[2];
total += l * l;
lo = min(lo, y);
hi = max(hi, y + l);
}
double target = total / 2.0;
for (int iter = 0; iter < 60; ++iter) {
double mid = (lo + hi) / 2.0;
if (areaBelow(squares, mid) >= target) hi = mid;
else lo = mid;
}
return hi;
}
private:
double areaBelow(vector<vector<int>>& squares, double yLine) {
double sum = 0.0;
for (auto& s : squares) {
double y = s[1], l = s[2];
if (yLine <= y) continue;
if (yLine >= y + l) sum += l * l;
else sum += l * (yLine - y);
}
return sum;
}
};class Solution:
def separateSquares(self, squares: List[List[int]]) -> float:
total = 0.0
lo = float("inf")
hi = float("-inf")
for _, y, l in squares:
total += l * l
lo = min(lo, y)
hi = max(hi, y + l)
target = total / 2.0
def area_below(y_line: float) -> float:
s = 0.0
for _, y, l in squares:
if y_line <= y:
continue
if y_line >= y + l:
s += l * l
else:
s += l * (y_line - y)
return s
for _ in range(60):
mid = (lo + hi) / 2.0
if area_below(mid) >= target:
hi = mid
else:
lo = mid
return hivar separateSquares = function(squares) {
let total = 0;
let lo = Infinity;
let hi = -Infinity;
for (const [x, y, l] of squares) {
total += l * l;
lo = Math.min(lo, y);
hi = Math.max(hi, y + l);
}
const target = total / 2;
const areaBelow = (yLine) => {
let sum = 0;
for (const [x, y, l] of squares) {
if (yLine <= y) continue;
if (yLine >= y + l) sum += l * l;
else sum += l * (yLine - y);
}
return sum;
};
for (let iter = 0; iter < 60; iter++) {
const mid = (lo + hi) / 2;
if (areaBelow(mid) >= target) hi = mid;
else lo = mid;
}
return hi;
};
Comments