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 (0)