Kimi LeetCode 3454. 分割正方形 II C++实现

这是 LeetCode 3454. 分割正方形 II 的 C++ 实现，基于扫描线 + 线段树算法。

核心思路

题目要求找到一条水平线 `y = k`，使得该线以上和以下的正方形并集面积相等。由于正方形可能重叠，需要使用扫描线算法：

1. 离散化 x 坐标：收集所有正方形的左右边界 x 值
2. 扫描线事件：每个正方形产生两个事件——下边界（加入，k=1）和上边界（移除，k=-1）
3. 线段树维护覆盖长度：在 y 轴上扫描时，用线段树维护当前 y 层被覆盖的 x 轴总长度（去重后的并集长度）
4. 两次扫描：第一次计算总面积，第二次找到面积恰好为一半时的 y 坐标

复杂度

- 时间复杂度：O(n log n)，其中 n 为正方形数量
- 空间复杂度：O(n)

C++ 代码

```cpp
class Solution {
public:
double separateSquares(vector<vector<int>>& squares) {
unordered_set<long long> xs_set;
vector<tuple<int, long long, long long, int>> events;

for (auto& sq : squares) {
long long x = sq[0], y = sq[1], l = sq[2];
long long x2 = x + l, y2 = y + l;
xs_set.insert(x);
xs_set.insert(x2);
events.emplace_back(y, x, x2, 1);
events.emplace_back(y2, x, x2, -1);
}

sort(events.begin(), events.end());

vector<long long> xs(xs_set.begin(), xs_set.end());
sort(xs.begin(), xs.end());

int n = xs.size();
// 离散化映射
unordered_map<long long, int> mp;
for (int i = 0; i < n; i++) mp[xs[i]] = i;

// 线段树
struct SegTree {
vector<int> cnt;
vector<long long> len;
vector<long long> xs;

SegTree(vector<long long>& xs) : xs(xs) {
int size = xs.size() * 4;
cnt.resize(size);
len.resize(size);
}

void update(int u, int l, int r, int cl, int cr, int k) {
if (cl > r || cr < l) return;
if (cl <= l && r <= cr) {
cnt[u] += k;
} else {
int mid = (l + r) >> 1;
update(u << 1, l, mid, cl, cr, k);
update(u << 1 | 1, mid + 1, r, cl, cr, k);
}
if (cnt[u] > 0) {
len[u] = xs[r + 1] - xs[l];
} else if (l == r) {
len[u] = 0;
} else {
len[u] = len[u << 1] + len[u << 1 | 1];
}
}
};

SegTree tree(xs);

double area = 0;
int prev_y = 0;

// 第一次扫描：计算总面积
for (auto& [y, x1, x2, k] : events) {
area += (double)(y - prev_y) * tree.len[1];
int l = mp[x1], r = mp[x2];
if (l < r) tree.update(1, 0, n - 2, l, r - 1, k);
prev_y = y;
}

double target = area / 2.0;
area = 0;
prev_y = 0;

// 重建线段树，第二次扫描
SegTree tree2(xs);

for (auto& [y, x1, x2, k] : events) {
double cur_len = tree2.len[1];
double t = (double)(y - prev_y) * cur_len;
if (area + t >= target) {
return (double)prev_y + (target - area) / cur_len;
}
area += t;
int l = mp[x1], r = mp[x2];
if (l < r) tree2.update(1, 0, n - 2, l, r - 1, k);
prev_y = y;
}

return 0.0;
}
};
```

关键细节

- 线段树区间表示：`xs` 存储离散化后的 x 坐标，`len[u]` 管理区间 `[xs[l], xs[r+1])`。`update` 中的 `pushup` 逻辑：若 `cnt[u] > 0`，则该区间被完全覆盖，长度为 `xs[r+1] - xs[l]`；否则合并子节点
- 区间更新：对于正方形 `[x1, x2)`，在线段树中更新索引范围 `[l, r-1]`（因为 `xs` 存储的是区间端点，线段树叶子节点对应相邻端点之间的区间）
- 两次扫描：第一次求总面积 `area`，第二次在扫描过程中累加面积，当累加值达到 `area/2` 时，用线性插值计算精确的 y 坐标

下载文件：