Finding the perfect horizontal line that splits a set of overlapping shapes into two equal areas is a classic geometry problem. When shapes overlap, we cannot simply sum their individual areas: we must find the area of their union, which adds a significant layer of complexity.
Problem Summary
You're given:
- An array of squares where each square is defined by its bottom-left corner and its side length .
- A scenario where squares may overlap, and overlapping regions are only counted once.
Your goal:
- Find the minimum -coordinate of a horizontal line such that the total area of the squares below the line is equal to the total area of the squares above the line.
Example 1: Input: squares = [[0,0,1],[2,2,1]]
Output: 1.00000
Explanation:
Any horizontal line between y = 1 and y = 2 results in an equal split, with 1 square unit above and 1 square unit below. The minimum y-value is 1.
Example 2: Input: squares = [[0,0,2],[1,1,1]]
Output: 1.00000
Explanation:
"
Since the blue square overlaps with the red square, it will not be counted again. Thus, the line y = 1 splits the squares into two equal parts.
Intuition
To solve this, we use a Sweep Line Algorithm combined with a Segment Tree. Imagine a horizontal line moving from the bottom-most -coordinate to the top-most. As this line moves, the "width" of the squares it intersects changes.
- Coordinate Compression: The -coordinates can be as large as , but there are at most unique -coordinates (start and end points of squares). we map these large values to a smaller range of indices to use them in a Segment Tree.
- The Sweep Line: we create events for the bottom and top of every square. As we sweep from bottom to top, we maintain the "active" horizontal width (the union of -intervals) using the Segment Tree.
- Area Calculation: The area between two -events is simply . By summing these, we get the total area.
- Finding the Median: Once we have the total area, we traverse the -stages again. When we reach the stage where the cumulative area hits , we use linear interpolation to find the exact -coordinate.
Code Blocks
C++ Solution
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
class Solution {
struct SegTree {
vector<int> count;
vector<long long> total_len;
const vector<int>& coords;
int n;
SegTree(const vector<int>& x_coords) : coords(x_coords) {
n = x_coords.size();
count.assign(4 * n, 0);
total_len.assign(4 * n, 0);
}
void update(int node, int start, int end, int L, int R, int val) {
if (L <= start && end <= R) {
count[node] += val;
} else {
int mid = (start + end) / 2;
if (L <= mid) update(2 * node, start, mid, L, R, val);
if (R > mid) update(2 * node + 1, mid + 1, end, L, R, val);
}
if (count[node] > 0) {
total_len[node] = coords[end + 1] - coords[start];
} else if (start != end) {
total_len[node] = total_len[2 * node] + total_len[2 * node + 1];
} else {
total_len[node] = 0;
}
}
};
public:
double separateSquares(vector<vector<int>>& squares) {
vector<int> x_coords;
vector<vector<int>> events;
for (auto& s : squares) {
x_coords.push_back(s[0]);
x_coords.push_back(s[0] + s[2]);
events.push_back({s[1], 1, s[0], s[0] + s[2]});
events.push_back({s[1] + s[2], -1, s[0], s[0] + s[2]});
}
sort(x_coords.begin(), x_coords.end());
x_coords.erase(unique(x_coords.begin(), x_coords.end()), x_coords.end());
sort(events.begin(), events.end());
SegTree st(x_coords);
vector<pair<double, long long>> stages;
double total_area = 0;
for (int i = 0; i < events.size() - 1; ++i) {
int L = lower_bound(x_coords.begin(), x_coords.end(), events[i][2]) - x_coords.begin();
int R = lower_bound(x_coords.begin(), x_coords.end(), events[i][3]) - x_coords.begin() - 1;
st.update(1, 0, x_coords.size() - 2, L, R, events[i][1]);
double height = events[i+1][0] - events[i][0];
long long width = st.total_len[1];
total_area += height * width;
stages.push_back({(double)events[i][0], width});
}
double half_area = total_area / 2.0;
double current_area = 0;
for (int i = 0; i < stages.size(); ++i) {
double next_y = (i + 1 < events.size() - 1) ? events[i+1][0] : events.back()[0];
double stage_area = (next_y - stages[i].first) * stages[i].second;
if (current_area + stage_area >= half_area - 1e-9) {
return stages[i].first + (half_area - current_area) / stages[i].second;
}
current_area += stage_area;
}
return events.back()[0];
}
};
Python Solution
from bisect import bisect_left
class SegTree:
def __init__(self, x_coords):
self.coords = x_coords
self.n = len(x_coords)
self.count = [0] * (4 * self.n)
self.total_len = [0] * (4 * self.n)
def update(self, node, start, end, L, R, val):
if L <= start and end <= R:
self.count[node] += val
else:
mid = (start + end) // 2
if L <= mid:
self.update(2 * node, start, mid, L, R, val)
if R > mid:
self.update(2 * node + 1, mid + 1, end, L, R, val)
if self.count[node] > 0:
self.total_len[node] = self.coords[end + 1] - self.coords[start]
elif start != end:
self.total_len[node] = self.total_len[2 * node] + self.total_len[2 * node + 1]
else:
self.total_len[node] = 0
class Solution:
def separateSquares(self, squares: list[list[int]]) -> float:
x_coords = sorted(list(set([s[0] for s in squares] + [s[0] + s[2] for s in squares])))
events = []
for x, y, l in squares:
events.append((y, 1, x, x + l))
events.append((y + l, -1, x, x + l))
events.sort()
st = SegTree(x_coords)
stages = []
total_area = 0
for i in range(len(events) - 1):
L = bisect_left(x_coords, events[i][2])
R = bisect_left(x_coords, events[i][3]) - 1
st.update(1, 0, len(x_coords) - 2, L, R, events[i][1])
height = events[i+1][0] - events[i][0]
width = st.total_len[1]
total_area += height * width
stages.append((events[i][0], width, events[i+1][0]))
half_area = total_area / 2.0
current_area = 0
for y_start, width, y_end in stages:
stage_area = (y_end - y_start) * width
if current_area + stage_area >= half_area - 1e-9:
if width == 0: return y_start
return y_start + (half_area - current_area) / width
current_area += stage_area
return events[-1][0]
JavaScript Solution
class SegTree {
constructor(xCoords) {
this.coords = xCoords;
this.n = xCoords.length;
this.count = new Int32Array(4 * this.n);
this.totalLen = new Float64Array(4 * this.n);
}
update(node, start, end, L, R, val) {
if (L <= start && end <= R) {
this.count[node] += val;
} else {
const mid = Math.floor((start + end) / 2);
if (L <= mid) this.update(2 * node, start, mid, L, R, val);
if (R > mid) this.update(2 * node + 1, mid + 1, end, L, R, val);
}
if (this.count[node] > 0) {
this.totalLen[node] = this.coords[end + 1] - this.coords[start];
} else if (start !== end) {
this.totalLen[node] = this.totalLen[2 * node] + this.totalLen[2 * node + 1];
} else {
this.totalLen[node] = 0;
}
}
}
var separateSquares = function(squares) {
let xSet = new Set();
for (const [x, y, l] of squares) {
xSet.add(x);
xSet.add(x + l);
}
const xCoords = Array.from(xSet).sort((a, b) => a - b);
const events = [];
for (const [x, y, l] of squares) {
events.push([y, 1, x, x + l]);
events.push([y + l, -1, x, x + l]);
}
events.sort((a, b) => a[0] - b[0]);
const st = new SegTree(xCoords);
const stages = [];
let totalArea = 0;
const findIdx = (val) => {
let low = 0, high = xCoords.length - 1;
while (low <= high) {
let mid = Math.floor((low + high) / 2);
if (xCoords[mid] < val) low = mid + 1;
else high = mid - 1;
}
return low;
};
for (let i = 0; i < events.length - 1; i++) {
const L = findIdx(events[i][2]);
const R = findIdx(events[i][3]) - 1;
st.update(1, 0, xCoords.length - 2, L, R, events[i][1]);
const height = events[i+1][0] - events[i][0];
const width = st.totalLen[1];
totalArea += height * width;
stages.push({ yStart: events[i][0], width, yEnd: events[i+1][0] });
}
const halfArea = totalArea / 2;
let currentArea = 0;
for (const stage of stages) {
const stageArea = (stage.yEnd - stage.yStart) * stage.width;
if (currentArea + stageArea >= halfArea - 1e-9) {
return stage.yStart + (halfArea - currentArea) / stage.width;
}
currentArea += stageArea;
}
return events[events.length - 1][0];
};
Key Takeaways
- Coordinate Compression: A vital technique when working with sparse but large ranges. It maps space into a manageable index space of size .
- Sweep Line Algorithm: This turns a 2D area problem into a 1D "length over time" problem. It is the standard approach for rectangle union problems.
- Segment Tree for Union: Unlike a standard Segment Tree that might store "sum" or "max", this version tracks the total covered length of intervals, even when those intervals overlap.
Final Thoughts
This problem is a fantastic example of how specialized data structures like Segment Trees are used in computational geometry. In the real world, these algorithms are foundational for VLSI Design (arranging components on a chip), Computer Graphics (rendering windows or sprites), and Geographic Information Systems (GIS). Mastering the sweep line technique will make you a much stronger candidate for high-level engineering roles that involve spatial reasoning.
Top comments (2)
This is one of those geometry problems that quietly tests whether you understand systems, not just math.
A lot of “area split” solutions die the moment overlap exists because they keep summing squares like the world is polite. It isn’t. Union area is where reality shows up.
What’s good here:
Sweep line framing is exactly right: turn 2D union area into “covered width over y-intervals” and integrate. That’s the whole game.
Segment tree storing covered length (not sum) is the key distinction. Counting overlaps doesn’t help — covered measure is what you need.
The “find y where cumulative area hits total/2” step is basically a continuous median problem, and linear interpolation inside the slab is the correct move.
Two tiny “don’t get cooked later” notes:
Handle width = 0 safely.
There can be y-intervals where no square is active, so interpolation would divide by zero. Your Python has the guard, JS/C++ should too (or skip those stages).
Storing stages:
You don’t need to keep a separate stages list with only (y, width) if you can just store (yStart, yEnd, width) as you sweep — it makes the second pass cleaner and avoids weird indexing assumptions.
Overall though: this is the clean, correct pattern for rectangle/square union + “split by area” problems. Once you learn this, a whole class of computational-geometry tasks stop being scary and start being mechanical.
Thank you so much sir for simplifying it even further for us!