LeetCode 3454: Separate Squares II (Line Sweep + Segment Tree for Union Area Split)
LeetCode 3454Sweep LineSegment TreeToday we solve LeetCode 3454 - Separate Squares II.
Source: https://leetcode.com/problems/separate-squares-ii/
English
Problem Summary
Given axis-aligned squares [x, y, l], define the area by the union of all squares (overlap counted once). Find the minimum horizontal line Y such that union area below Y equals union area above Y.
Key Insight
For union area, we should not sum each square independently. Instead, do a y-sweep:
1) Convert each square into two events: entering at y, leaving at y+l with x-interval [x, x+l).
2) Between two consecutive y-levels, active x-union length is constant.
3) Strip area = coveredX * deltaY.
Using a segment tree over compressed x coordinates, we can maintain current covered x-length in O(log n) per event update.
Algorithm
1) Build events and x-coordinate compression.
2) Sweep once to compute total union area.
3) Sweep again and accumulate strip areas; when accumulated area reaches total/2, answer lies in current strip.
4) In that strip, covered x-length is constant, so solve linearly:
ansY = y0 + (target - prefixArea) / coveredX.
Complexity Analysis
Let n be number of squares, events = 2n.
Time: O(n log n) (sorting + segment tree updates).
Space: O(n).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
import java.util.*;
class Solution {
static class Event {
long y, x1, x2;
int type;
Event(long y, long x1, long x2, int type) {
this.y = y; this.x1 = x1; this.x2 = x2; this.type = type;
}
}
static class SegTree {
int n;
int[] cover;
double[] len;
long[] xs;
SegTree(long[] xs) {
this.xs = xs;
this.n = xs.length - 1;
this.cover = new int[n * 4 + 5];
this.len = new double[n * 4 + 5];
}
void update(int idx, int l, int r, int ql, int qr, int delta) {
if (ql > r || qr < l) return;
if (ql <= l && r <= qr) {
cover[idx] += delta;
pushUp(idx, l, r);
return;
}
int mid = (l + r) >>> 1;
update(idx << 1, l, mid, ql, qr, delta);
update(idx << 1 | 1, mid + 1, r, ql, qr, delta);
pushUp(idx, l, r);
}
void pushUp(int idx, int l, int r) {
if (cover[idx] > 0) {
len[idx] = xs[r + 1] - xs[l];
} else if (l == r) {
len[idx] = 0;
} else {
len[idx] = len[idx << 1] + len[idx << 1 | 1];
}
}
double totalLen() { return n <= 0 ? 0.0 : len[1]; }
}
public double separateSquares(int[][] squares) {
List<Event> events = new ArrayList<>();
List<Long> xVals = new ArrayList<>();
for (int[] s : squares) {
long x = s[0], y = s[1], l = s[2];
long x2 = x + l, y2 = y + l;
events.add(new Event(y, x, x2, +1));
events.add(new Event(y2, x, x2, -1));
xVals.add(x);
xVals.add(x2);
}
Collections.sort(xVals);
long[] xs = xVals.stream().distinct().mapToLong(Long::longValue).toArray();
Map<Long, Integer> xi = new HashMap<>();
for (int i = 0; i < xs.length; i++) xi.put(xs[i], i);
events.sort(Comparator.comparingLong(e -> e.y));
double total = sweepArea(events, xs, xi, -1.0);
double target = total / 2.0;
return sweepArea(events, xs, xi, target);
}
private double sweepArea(List<Event> events, long[] xs, Map<Long, Integer> xi, double target) {
SegTree st = new SegTree(xs);
int m = events.size();
int i = 0;
long prevY = events.get(0).y;
double acc = 0.0;
while (i < m) {
long y = events.get(i).y;
double covered = st.totalLen();
double strip = covered * (y - prevY);
if (target >= 0 && covered > 0 && acc + strip >= target) {
return prevY + (target - acc) / covered;
}
acc += strip;
while (i < m && events.get(i).y == y) {
Event e = events.get(i++);
int l = xi.get(e.x1), r = xi.get(e.x2) - 1;
if (l <= r) st.update(1, 0, st.n - 1, l, r, e.type);
}
prevY = y;
}
return target < 0 ? acc : prevY;
}
}import "sort"
type Event struct {
y, x1, x2 int64
typ int
}
type SegTree struct {
n int
cover []int
length []float64
xs []int64
}
func NewSegTree(xs []int64) *SegTree {
n := len(xs) - 1
return &SegTree{n: n, cover: make([]int, 4*n+5), length: make([]float64, 4*n+5), xs: xs}
}
func (st *SegTree) pushUp(idx, l, r int) {
if st.cover[idx] > 0 {
st.length[idx] = float64(st.xs[r+1] - st.xs[l])
} else if l == r {
st.length[idx] = 0
} else {
st.length[idx] = st.length[idx*2] + st.length[idx*2+1]
}
}
func (st *SegTree) update(idx, l, r, ql, qr, delta int) {
if ql > r || qr < l {
return
}
if ql <= l && r <= qr {
st.cover[idx] += delta
st.pushUp(idx, l, r)
return
}
mid := (l + r) / 2
st.update(idx*2, l, mid, ql, qr, delta)
st.update(idx*2+1, mid+1, r, ql, qr, delta)
st.pushUp(idx, l, r)
}
func (st *SegTree) totalLen() float64 {
if st.n <= 0 { return 0 }
return st.length[1]
}
func separateSquares(squares [][]int) float64 {
events := make([]Event, 0, len(squares)*2)
xVals := make([]int64, 0, len(squares)*2)
for _, s := range squares {
x, y, l := int64(s[0]), int64(s[1]), int64(s[2])
x2, y2 := x+l, y+l
events = append(events, Event{y, x, x2, 1}, Event{y2, x, x2, -1})
xVals = append(xVals, x, x2)
}
sort.Slice(xVals, func(i, j int) bool { return xVals[i] < xVals[j] })
xs := make([]int64, 0, len(xVals))
for _, x := range xVals {
if len(xs) == 0 || xs[len(xs)-1] != x { xs = append(xs, x) }
}
xi := map[int64]int{}
for i, x := range xs { xi[x] = i }
sort.Slice(events, func(i, j int) bool { return events[i].y < events[j].y })
total := sweep(events, xs, xi, -1)
return sweep(events, xs, xi, total/2.0)
}
func sweep(events []Event, xs []int64, xi map[int64]int, target float64) float64 {
st := NewSegTree(xs)
i, m := 0, len(events)
prevY := events[0].y
acc := 0.0
for i < m {
y := events[i].y
covered := st.totalLen()
strip := covered * float64(y-prevY)
if target >= 0 && covered > 0 && acc+strip >= target {
return float64(prevY) + (target-acc)/covered
}
acc += strip
for i < m && events[i].y == y {
e := events[i]
i++
l, r := xi[e.x1], xi[e.x2]-1
if l <= r {
st.update(1, 0, st.n-1, l, r, e.typ)
}
}
prevY = y
}
if target < 0 { return acc }
return float64(prevY)
}class Solution {
struct Event {
long long y, x1, x2;
int type;
bool operator<(const Event& other) const { return y < other.y; }
};
struct SegTree {
int n;
vector<int> cover;
vector<double> len;
vector<long long> xs;
SegTree(const vector<long long>& x): xs(x) {
n = (int)xs.size() - 1;
cover.assign(4 * n + 5, 0);
len.assign(4 * n + 5, 0.0);
}
void pushUp(int idx, int l, int r) {
if (cover[idx] > 0) len[idx] = (double)(xs[r + 1] - xs[l]);
else if (l == r) len[idx] = 0.0;
else len[idx] = len[idx * 2] + len[idx * 2 + 1];
}
void update(int idx, int l, int r, int ql, int qr, int delta) {
if (ql > r || qr < l) return;
if (ql <= l && r <= qr) {
cover[idx] += delta;
pushUp(idx, l, r);
return;
}
int mid = (l + r) / 2;
update(idx * 2, l, mid, ql, qr, delta);
update(idx * 2 + 1, mid + 1, r, ql, qr, delta);
pushUp(idx, l, r);
}
double totalLen() const { return n <= 0 ? 0.0 : len[1]; }
};
double sweep(const vector<Event>& events, const vector<long long>& xs,
unordered_map<long long, int>& xi, double target) {
SegTree st(xs);
int i = 0, m = events.size();
long long prevY = events[0].y;
double acc = 0.0;
while (i < m) {
long long y = events[i].y;
double covered = st.totalLen();
double strip = covered * (double)(y - prevY);
if (target >= 0 && covered > 0 && acc + strip >= target) {
return (double)prevY + (target - acc) / covered;
}
acc += strip;
while (i < m && events[i].y == y) {
auto& e = events[i++];
int l = xi[e.x1], r = xi[e.x2] - 1;
if (l <= r) st.update(1, 0, st.n - 1, l, r, e.type);
}
prevY = y;
}
return target < 0 ? acc : (double)prevY;
}
public:
double separateSquares(vector<vector<int>>& squares) {
vector<Event> events;
vector<long long> xVals;
for (auto& s : squares) {
long long x = s[0], y = s[1], l = s[2];
long long x2 = x + l, y2 = y + l;
events.push_back({y, x, x2, +1});
events.push_back({y2, x, x2, -1});
xVals.push_back(x);
xVals.push_back(x2);
}
sort(xVals.begin(), xVals.end());
xVals.erase(unique(xVals.begin(), xVals.end()), xVals.end());
unordered_map<long long, int> xi;
for (int i = 0; i < (int)xVals.size(); ++i) xi[xVals[i]] = i;
sort(events.begin(), events.end());
double total = sweep(events, xVals, xi, -1.0);
return sweep(events, xVals, xi, total / 2.0);
}
};from typing import List
class Solution:
def separateSquares(self, squares: List[List[int]]) -> float:
events = []
xs = []
for x, y, l in squares:
x2, y2 = x + l, y + l
events.append((y, x, x2, 1))
events.append((y2, x, x2, -1))
xs.extend([x, x2])
xs = sorted(set(xs))
xi = {x: i for i, x in enumerate(xs)}
events.sort()
n = len(xs) - 1
cover = [0] * (4 * max(1, n) + 5)
length = [0.0] * (4 * max(1, n) + 5)
def push_up(idx: int, l: int, r: int) -> None:
if cover[idx] > 0:
length[idx] = xs[r + 1] - xs[l]
elif l == r:
length[idx] = 0.0
else:
length[idx] = length[idx * 2] + length[idx * 2 + 1]
def update(idx: int, l: int, r: int, ql: int, qr: int, delta: int) -> None:
if ql > r or qr < l:
return
if ql <= l and r <= qr:
cover[idx] += delta
push_up(idx, l, r)
return
mid = (l + r) // 2
update(idx * 2, l, mid, ql, qr, delta)
update(idx * 2 + 1, mid + 1, r, ql, qr, delta)
push_up(idx, l, r)
def total_len() -> float:
return 0.0 if n <= 0 else length[1]
def sweep(target: float) -> float:
i = 0
m = len(events)
prev_y = events[0][0]
acc = 0.0
while i < m:
y = events[i][0]
covered = total_len()
strip = covered * (y - prev_y)
if target >= 0 and covered > 0 and acc + strip >= target:
return prev_y + (target - acc) / covered
acc += strip
while i < m and events[i][0] == y:
_, x1, x2, typ = events[i]
i += 1
l, r = xi[x1], xi[x2] - 1
if n > 0 and l <= r:
update(1, 0, n - 1, l, r, typ)
prev_y = y
return acc if target < 0 else float(prev_y)
total = sweep(-1.0)
# reset tree for second sweep
for i in range(len(cover)):
cover[i] = 0
length[i] = 0.0
return sweep(total / 2.0)var separateSquares = function(squares) {
const events = [];
const xVals = [];
for (const [x, y, l] of squares) {
const x2 = x + l, y2 = y + l;
events.push([y, x, x2, 1]);
events.push([y2, x, x2, -1]);
xVals.push(x, x2);
}
xVals.sort((a, b) => a - b);
const xs = [];
for (const x of xVals) {
if (xs.length === 0 || xs[xs.length - 1] !== x) xs.push(x);
}
const xi = new Map();
xs.forEach((x, i) => xi.set(x, i));
events.sort((a, b) => a[0] - b[0]);
const n = xs.length - 1;
const cover = new Array(4 * Math.max(1, n) + 5).fill(0);
const len = new Array(4 * Math.max(1, n) + 5).fill(0);
const pushUp = (idx, l, r) => {
if (cover[idx] > 0) {
len[idx] = xs[r + 1] - xs[l];
} else if (l === r) {
len[idx] = 0;
} else {
len[idx] = len[idx * 2] + len[idx * 2 + 1];
}
};
const update = (idx, l, r, ql, qr, delta) => {
if (ql > r || qr < l) return;
if (ql <= l && r <= qr) {
cover[idx] += delta;
pushUp(idx, l, r);
return;
}
const mid = (l + r) >> 1;
update(idx * 2, l, mid, ql, qr, delta);
update(idx * 2 + 1, mid + 1, r, ql, qr, delta);
pushUp(idx, l, r);
};
const totalLen = () => (n <= 0 ? 0 : len[1]);
const sweep = (target) => {
let i = 0;
let prevY = events[0][0];
let acc = 0;
while (i < events.length) {
const y = events[i][0];
const covered = totalLen();
const strip = covered * (y - prevY);
if (target >= 0 && covered > 0 && acc + strip >= target) {
return prevY + (target - acc) / covered;
}
acc += strip;
while (i < events.length && events[i][0] === y) {
const [, x1, x2, typ] = events[i++];
const l = xi.get(x1), r = xi.get(x2) - 1;
if (n > 0 && l <= r) update(1, 0, n - 1, l, r, typ);
}
prevY = y;
}
return target < 0 ? acc : prevY;
};
const total = sweep(-1);
cover.fill(0);
len.fill(0);
return sweep(total / 2);
};中文
题目概述
给定多个轴对齐正方形 [x, y, l]，面积按并集计算（重叠只算一次）。要求找到最小水平线 Y，使得线下并集面积等于线上并集面积。
核心思路
这题和 I 最大区别是“重叠不能重复计数”，所以不能逐个正方形累加，要做扫描线：
1）每个正方形拆成两个 y 事件：y 进入、y+l 离开，对应 x 区间 [x, x+l)。
2）相邻两条事件 y 之间，当前被覆盖的 x 总长度不变。
3）这一条横向条带面积 = coveredX * deltaY。
用“x 坐标压缩 + 线段树维护覆盖长度”即可在 O(log n) 更新活跃区间。
算法步骤
1）构建事件并做 x 坐标离散化。
2）第一遍扫描得到并集总面积 total。
3）第二遍扫描累计面积，首次达到 total/2 时答案就在当前条带。
4）条带内覆盖长度恒定，直接线性插值：
ansY = y0 + (target - prefixArea) / coveredX。
复杂度分析
设正方形数量为 n，事件数 2n。
时间复杂度：O(n log n)。
空间复杂度：O(n)。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
import java.util.*;
class Solution {
static class Event {
long y, x1, x2;
int type;
Event(long y, long x1, long x2, int type) {
this.y = y; this.x1 = x1; this.x2 = x2; this.type = type;
}
}
static class SegTree {
int n;
int[] cover;
double[] len;
long[] xs;
SegTree(long[] xs) {
this.xs = xs;
this.n = xs.length - 1;
this.cover = new int[n * 4 + 5];
this.len = new double[n * 4 + 5];
}
void update(int idx, int l, int r, int ql, int qr, int delta) {
if (ql > r || qr < l) return;
if (ql <= l && r <= qr) {
cover[idx] += delta;
pushUp(idx, l, r);
return;
}
int mid = (l + r) >>> 1;
update(idx << 1, l, mid, ql, qr, delta);
update(idx << 1 | 1, mid + 1, r, ql, qr, delta);
pushUp(idx, l, r);
}
void pushUp(int idx, int l, int r) {
if (cover[idx] > 0) {
len[idx] = xs[r + 1] - xs[l];
} else if (l == r) {
len[idx] = 0;
} else {
len[idx] = len[idx << 1] + len[idx << 1 | 1];
}
}
double totalLen() { return n <= 0 ? 0.0 : len[1]; }
}
public double separateSquares(int[][] squares) {
List<Event> events = new ArrayList<>();
List<Long> xVals = new ArrayList<>();
for (int[] s : squares) {
long x = s[0], y = s[1], l = s[2];
long x2 = x + l, y2 = y + l;
events.add(new Event(y, x, x2, +1));
events.add(new Event(y2, x, x2, -1));
xVals.add(x);
xVals.add(x2);
}
Collections.sort(xVals);
long[] xs = xVals.stream().distinct().mapToLong(Long::longValue).toArray();
Map<Long, Integer> xi = new HashMap<>();
for (int i = 0; i < xs.length; i++) xi.put(xs[i], i);
events.sort(Comparator.comparingLong(e -> e.y));
double total = sweepArea(events, xs, xi, -1.0);
double target = total / 2.0;
return sweepArea(events, xs, xi, target);
}
private double sweepArea(List<Event> events, long[] xs, Map<Long, Integer> xi, double target) {
SegTree st = new SegTree(xs);
int m = events.size();
int i = 0;
long prevY = events.get(0).y;
double acc = 0.0;
while (i < m) {
long y = events.get(i).y;
double covered = st.totalLen();
double strip = covered * (y - prevY);
if (target >= 0 && covered > 0 && acc + strip >= target) {
return prevY + (target - acc) / covered;
}
acc += strip;
while (i < m && events.get(i).y == y) {
Event e = events.get(i++);
int l = xi.get(e.x1), r = xi.get(e.x2) - 1;
if (l <= r) st.update(1, 0, st.n - 1, l, r, e.type);
}
prevY = y;
}
return target < 0 ? acc : prevY;
}
}import "sort"
type Event struct {
y, x1, x2 int64
typ int
}
type SegTree struct {
n int
cover []int
length []float64
xs []int64
}
func NewSegTree(xs []int64) *SegTree {
n := len(xs) - 1
return &SegTree{n: n, cover: make([]int, 4*n+5), length: make([]float64, 4*n+5), xs: xs}
}
func (st *SegTree) pushUp(idx, l, r int) {
if st.cover[idx] > 0 {
st.length[idx] = float64(st.xs[r+1] - st.xs[l])
} else if l == r {
st.length[idx] = 0
} else {
st.length[idx] = st.length[idx*2] + st.length[idx*2+1]
}
}
func (st *SegTree) update(idx, l, r, ql, qr, delta int) {
if ql > r || qr < l {
return
}
if ql <= l && r <= qr {
st.cover[idx] += delta
st.pushUp(idx, l, r)
return
}
mid := (l + r) / 2
st.update(idx*2, l, mid, ql, qr, delta)
st.update(idx*2+1, mid+1, r, ql, qr, delta)
st.pushUp(idx, l, r)
}
func (st *SegTree) totalLen() float64 {
if st.n <= 0 { return 0 }
return st.length[1]
}
func separateSquares(squares [][]int) float64 {
events := make([]Event, 0, len(squares)*2)
xVals := make([]int64, 0, len(squares)*2)
for _, s := range squares {
x, y, l := int64(s[0]), int64(s[1]), int64(s[2])
x2, y2 := x+l, y+l
events = append(events, Event{y, x, x2, 1}, Event{y2, x, x2, -1})
xVals = append(xVals, x, x2)
}
sort.Slice(xVals, func(i, j int) bool { return xVals[i] < xVals[j] })
xs := make([]int64, 0, len(xVals))
for _, x := range xVals {
if len(xs) == 0 || xs[len(xs)-1] != x { xs = append(xs, x) }
}
xi := map[int64]int{}
for i, x := range xs { xi[x] = i }
sort.Slice(events, func(i, j int) bool { return events[i].y < events[j].y })
total := sweep(events, xs, xi, -1)
return sweep(events, xs, xi, total/2.0)
}
func sweep(events []Event, xs []int64, xi map[int64]int, target float64) float64 {
st := NewSegTree(xs)
i, m := 0, len(events)
prevY := events[0].y
acc := 0.0
for i < m {
y := events[i].y
covered := st.totalLen()
strip := covered * float64(y-prevY)
if target >= 0 && covered > 0 && acc+strip >= target {
return float64(prevY) + (target-acc)/covered
}
acc += strip
for i < m && events[i].y == y {
e := events[i]
i++
l, r := xi[e.x1], xi[e.x2]-1
if l <= r {
st.update(1, 0, st.n-1, l, r, e.typ)
}
}
prevY = y
}
if target < 0 { return acc }
return float64(prevY)
}class Solution {
struct Event {
long long y, x1, x2;
int type;
bool operator<(const Event& other) const { return y < other.y; }
};
struct SegTree {
int n;
vector<int> cover;
vector<double> len;
vector<long long> xs;
SegTree(const vector<long long>& x): xs(x) {
n = (int)xs.size() - 1;
cover.assign(4 * n + 5, 0);
len.assign(4 * n + 5, 0.0);
}
void pushUp(int idx, int l, int r) {
if (cover[idx] > 0) len[idx] = (double)(xs[r + 1] - xs[l]);
else if (l == r) len[idx] = 0.0;
else len[idx] = len[idx * 2] + len[idx * 2 + 1];
}
void update(int idx, int l, int r, int ql, int qr, int delta) {
if (ql > r || qr < l) return;
if (ql <= l && r <= qr) {
cover[idx] += delta;
pushUp(idx, l, r);
return;
}
int mid = (l + r) / 2;
update(idx * 2, l, mid, ql, qr, delta);
update(idx * 2 + 1, mid + 1, r, ql, qr, delta);
pushUp(idx, l, r);
}
double totalLen() const { return n <= 0 ? 0.0 : len[1]; }
};
double sweep(const vector<Event>& events, const vector<long long>& xs,
unordered_map<long long, int>& xi, double target) {
SegTree st(xs);
int i = 0, m = events.size();
long long prevY = events[0].y;
double acc = 0.0;
while (i < m) {
long long y = events[i].y;
double covered = st.totalLen();
double strip = covered * (double)(y - prevY);
if (target >= 0 && covered > 0 && acc + strip >= target) {
return (double)prevY + (target - acc) / covered;
}
acc += strip;
while (i < m && events[i].y == y) {
auto& e = events[i++];
int l = xi[e.x1], r = xi[e.x2] - 1;
if (l <= r) st.update(1, 0, st.n - 1, l, r, e.type);
}
prevY = y;
}
return target < 0 ? acc : (double)prevY;
}
public:
double separateSquares(vector<vector<int>>& squares) {
vector<Event> events;
vector<long long> xVals;
for (auto& s : squares) {
long long x = s[0], y = s[1], l = s[2];
long long x2 = x + l, y2 = y + l;
events.push_back({y, x, x2, +1});
events.push_back({y2, x, x2, -1});
xVals.push_back(x);
xVals.push_back(x2);
}
sort(xVals.begin(), xVals.end());
xVals.erase(unique(xVals.begin(), xVals.end()), xVals.end());
unordered_map<long long, int> xi;
for (int i = 0; i < (int)xVals.size(); ++i) xi[xVals[i]] = i;
sort(events.begin(), events.end());
double total = sweep(events, xVals, xi, -1.0);
return sweep(events, xVals, xi, total / 2.0);
}
};from typing import List
class Solution:
def separateSquares(self, squares: List[List[int]]) -> float:
events = []
xs = []
for x, y, l in squares:
x2, y2 = x + l, y + l
events.append((y, x, x2, 1))
events.append((y2, x, x2, -1))
xs.extend([x, x2])
xs = sorted(set(xs))
xi = {x: i for i, x in enumerate(xs)}
events.sort()
n = len(xs) - 1
cover = [0] * (4 * max(1, n) + 5)
length = [0.0] * (4 * max(1, n) + 5)
def push_up(idx: int, l: int, r: int) -> None:
if cover[idx] > 0:
length[idx] = xs[r + 1] - xs[l]
elif l == r:
length[idx] = 0.0
else:
length[idx] = length[idx * 2] + length[idx * 2 + 1]
def update(idx: int, l: int, r: int, ql: int, qr: int, delta: int) -> None:
if ql > r or qr < l:
return
if ql <= l and r <= qr:
cover[idx] += delta
push_up(idx, l, r)
return
mid = (l + r) // 2
update(idx * 2, l, mid, ql, qr, delta)
update(idx * 2 + 1, mid + 1, r, ql, qr, delta)
push_up(idx, l, r)
def total_len() -> float:
return 0.0 if n <= 0 else length[1]
def sweep(target: float) -> float:
i = 0
m = len(events)
prev_y = events[0][0]
acc = 0.0
while i < m:
y = events[i][0]
covered = total_len()
strip = covered * (y - prev_y)
if target >= 0 and covered > 0 and acc + strip >= target:
return prev_y + (target - acc) / covered
acc += strip
while i < m and events[i][0] == y:
_, x1, x2, typ = events[i]
i += 1
l, r = xi[x1], xi[x2] - 1
if n > 0 and l <= r:
update(1, 0, n - 1, l, r, typ)
prev_y = y
return acc if target < 0 else float(prev_y)
total = sweep(-1.0)
# reset tree for second sweep
for i in range(len(cover)):
cover[i] = 0
length[i] = 0.0
return sweep(total / 2.0)var separateSquares = function(squares) {
const events = [];
const xVals = [];
for (const [x, y, l] of squares) {
const x2 = x + l, y2 = y + l;
events.push([y, x, x2, 1]);
events.push([y2, x, x2, -1]);
xVals.push(x, x2);
}
xVals.sort((a, b) => a - b);
const xs = [];
for (const x of xVals) {
if (xs.length === 0 || xs[xs.length - 1] !== x) xs.push(x);
}
const xi = new Map();
xs.forEach((x, i) => xi.set(x, i));
events.sort((a, b) => a[0] - b[0]);
const n = xs.length - 1;
const cover = new Array(4 * Math.max(1, n) + 5).fill(0);
const len = new Array(4 * Math.max(1, n) + 5).fill(0);
const pushUp = (idx, l, r) => {
if (cover[idx] > 0) {
len[idx] = xs[r + 1] - xs[l];
} else if (l === r) {
len[idx] = 0;
} else {
len[idx] = len[idx * 2] + len[idx * 2 + 1];
}
};
const update = (idx, l, r, ql, qr, delta) => {
if (ql > r || qr < l) return;
if (ql <= l && r <= qr) {
cover[idx] += delta;
pushUp(idx, l, r);
return;
}
const mid = (l + r) >> 1;
update(idx * 2, l, mid, ql, qr, delta);
update(idx * 2 + 1, mid + 1, r, ql, qr, delta);
pushUp(idx, l, r);
};
const totalLen = () => (n <= 0 ? 0 : len[1]);
const sweep = (target) => {
let i = 0;
let prevY = events[0][0];
let acc = 0;
while (i < events.length) {
const y = events[i][0];
const covered = totalLen();
const strip = covered * (y - prevY);
if (target >= 0 && covered > 0 && acc + strip >= target) {
return prevY + (target - acc) / covered;
}
acc += strip;
while (i < events.length && events[i][0] === y) {
const [, x1, x2, typ] = events[i++];
const l = xi.get(x1), r = xi.get(x2) - 1;
if (n > 0 && l <= r) update(1, 0, n - 1, l, r, typ);
}
prevY = y;
}
return target < 0 ? acc : prevY;
};
const total = sweep(-1);
cover.fill(0);
len.fill(0);
return sweep(total / 2);
};
Comments