Imagine you have a collection of square stickers scattered across a wall, and you want to draw one perfectly horizontal line that splits the total area of those stickers exactly in half. This problem challenges us to find the vertical "balancing point" of multiple overlapping or separate shapes, a task that requires both geometric intuition and efficient data processing.
Problem Summary
You're given:
- A 2D array of squares where each square is defined by its bottom-left coordinates () and its side length .
- The knowledge that squares can overlap, and overlapping areas count multiple times.
Your goal:
- Find the minimum -coordinate of a horizontal line such that the total area below the line is equal to the total area 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 will have 1 square unit above it and 1 square unit below it. The lowest option is 1.
Example 2:
Input: squares = [[0,0,2],[1,1,1]]
Output: 1.16667
"
Explanation:
The areas are:
Below the line: 7/6 * 2 (Red) + 1/6 (Blue) = 15/6 = 2.5.
Above the line: 5/6 * 2 (Red) + 5/6 (Blue) = 15/6 = 2.5.
Since the areas above and below the line are equal, the output is 7/6 = 1.16667.
Intuition
To solve this, we need to think about how the total area changes as we move a horizontal line from the bottom to the top.
- Total Area Calculation: First, calculate the total area of all squares. Since side length is , the area of one square is . The "target" area we want below our line is exactly half of this total sum.
- Event Processing: We can treat the bottom and top edges of each square as "events." A square starts contributing its width to our "active width" at its bottom and stops at its top .
The Sweep-Line: If we sort these -coordinates and move upward, the area accumulated between two -levels is simply:
Finding the Split: As we sweep upward, we keep adding to our cumulative area. The moment our next step would exceed the "halfway" area, we know the line must exist between the previous and the current . We then use simple algebra to find the exact decimal coordinate.
Code Blocks
C++
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
class Solution {
public:
double separateSquares(vector<vector<int>>& squares) {
double totalArea = 0;
vector<pair<int, int>> events; // {y_coordinate, type_and_width}
for (const auto& s : squares) {
long long x = s[0], y = s[1], l = s[2];
totalArea += (double)l * l;
// Use positive width for start, negative for end
events.push_back({y, l});
events.push_back({y + l, -l});
}
// Sort events by y-coordinate
sort(events.begin(), events.end());
double targetArea = totalArea / 2.0;
double currentArea = 0;
long long currentWidth = 0;
int prevY = events[0].first;
for (const auto& event : events) {
int currY = event.first;
long long heightDiff = currY - prevY;
double areaIncrease = (double)currentWidth * heightDiff;
if (currentArea + areaIncrease >= targetArea) {
// The line is within this horizontal strip
double neededArea = targetArea - currentArea;
return prevY + (neededArea / currentWidth);
}
currentArea += areaIncrease;
currentWidth += event.second;
prevY = currY;
}
return 0.0;
}
};
Python
class Solution:
def separateSquares(self, squares: List[List[int]]) -> float:
total_area = 0
events = []
for x, y, l in squares:
total_area += l * l
# Event: (y-coordinate, width_change)
events.append((y, l))
events.append((y + l, -l))
# Sort by y-coordinate
events.sort()
target_area = total_area / 2.0
current_area = 0.0
current_width = 0
prev_y = events[0][0]
for curr_y, width_change in events:
height_diff = curr_y - prev_y
area_increase = current_width * height_diff
if current_area + area_increase >= target_area:
needed_area = target_area - current_area
return prev_y + (needed_area / current_width)
current_area += area_increase
current_width += width_change
prev_y = curr_y
return 0.0
JavaScript
/**
* @param {number[][]} squares
* @return {number}
*/
var separateSquares = function(squares) {
let totalArea = 0;
let events = [];
for (let [x, y, l] of squares) {
totalArea += l * l;
events.push([y, l]);
events.push([y + l, -l]);
}
// Sort by y-coordinate
events.sort((a, b) => a[0] - b[0]);
let targetArea = totalArea / 2.0;
let currentArea = 0;
let currentWidth = 0;
let prevY = events[0][0];
for (let [currY, widthChange] of events) {
let heightDiff = currY - prevY;
let areaIncrease = currentWidth * heightDiff;
if (currentArea + areaIncrease >= targetArea) {
let neededArea = targetArea - currentArea;
return prevY + (neededArea / currentWidth);
}
currentArea += areaIncrease;
currentWidth += widthChange;
prevY = currY;
}
return 0.0;
};
Key Takeaways
- Sweep-Line Technique: A powerful way to solve 2D geometry problems by "scanning" the plane in one direction (usually or ).
- Event-Based Processing: Instead of looking at every coordinate, we only focus on points where the state changes (the edges of the squares).
- Linear Interpolation: Once we find the interval containing our answer, we use the ratio of the remaining area to the current width to find the exact vertical position.
Final Thoughts
This problem is a fantastic introduction to computational geometry. While the C++ solution provided in the prompt used highly optimized low-level tricks like SIMD (AVX2) and Radix Sort to squeeze out every millisecond of performance, the core logic remains the sweep-line approach.
In real-world systems, these types of algorithms are used in Computer-Aided Design (CAD) software to calculate centers of mass, and in Rendering Engines to determine which objects are visible at certain layers. Understanding how to "discretize" a continuous problem into events is a key skill for any senior engineer.
Top comments (0)