这是 LeetCode 3454. 分割正方形 II 的 C 实现基于扫描线 线段树算法。核心思路题目要求找到一条水平线 y k使得该线以上和以下的正方形并集面积相等。由于正方形可能重叠需要使用扫描线算法1. 离散化 x 坐标收集所有正方形的左右边界 x 值2. 扫描线事件每个正方形产生两个事件——下边界加入k1和上边界移除k-13. 线段树维护覆盖长度在 y 轴上扫描时用线段树维护当前 y 层被覆盖的 x 轴总长度去重后的并集长度4. 两次扫描第一次计算总面积第二次找到面积恰好为一半时的 y 坐标复杂度- 时间复杂度O(n log n)其中 n 为正方形数量- 空间复杂度O(n)C 代码cppclass Solution {public:double separateSquares(vectorvectorint squares) {unordered_setlong long xs_set;vectortupleint, 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());vectorlong long xs(xs_set.begin(), xs_set.end());sort(xs.begin(), xs.end());int n xs.size();// 离散化映射unordered_maplong long, int mp;for (int i 0; i n; i) mp[xs[i]] i;// 线段树struct SegTree {vectorint cnt;vectorlong long len;vectorlong long xs;SegTree(vectorlong 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[r1])。update 中的 pushup 逻辑若 cnt[u] 0则该区间被完全覆盖长度为 xs[r1] - xs[l]否则合并子节点- 区间更新对于正方形 [x1, x2)在线段树中更新索引范围 [l, r-1]因为 xs 存储的是区间端点线段树叶子节点对应相邻端点之间的区间- 两次扫描第一次求总面积 area第二次在扫描过程中累加面积当累加值达到 area/2 时用线性插值计算精确的 y 坐标下载文件