Hard

题目描述

给定一个二维整数数组 squares。每个 squares[i] = [xi, yi, li] 表示一个与x轴平行的正方形的左下角坐标和边长。

找到一条水平线的最小y坐标值，使得该线上方正方形覆盖的总面积等于该线下方正方形覆盖的总面积。

答案误差在 10^-5 以内将被接受。

注意：正方形可能重叠。重叠区域在此版本中只计算一次。

示例 1：

输入：squares = [[0,0,1],[2,2,1]]
输出：1.00000
解释：y = 1 到 y = 2 之间的任何水平线都会产生相等的分割，上方和下方各有1个平方单位。最小y值是1。

示例 2：

输入：squares = [[0,0,2],[1,1,1]]
输出：1.00000
解释：由于蓝色正方形与红色正方形重叠，重叠部分不会重复计算。因此，线 y = 1 将正方形分成两个相等的部分。

约束条件：

  • 1 <= squares.length <= 5 * 10^4
  • squares[i] = [xi, yi, li]
  • squares[i].length == 3
  • 0 <= xi, yi <= 10^9
  • 1 <= li <= 10^9
  • 所有正方形的总面积不超过 10^15

提示：

  • 使用线性扫描和线段树
  • 分割线必须位于某个正方形内部

解题思路

这是一道几何计算的复杂题目。解决思路分为以下几步：

  1. 关键观察：分割线的最优位置必定经过某个正方形的边界，因为只有在这些关键位置面积分布才可能发生变化。

  2. 扫描线算法：我们需要从下到上扫描所有可能的y坐标。对于每个y坐标，计算该水平线上方和下方的总面积。

  3. 面积计算：由于正方形可能重叠，我们需要使用线段树或其他数据结构来高效计算不重复的面积。具体做法是：

    • 对于每个y坐标，收集所有与该水平线相交的正方形
    • 计算这些正方形在该水平线上方和下方的投影面积
    • 使用区间合并技术处理重叠部分

  4. 二分搜索优化：由于面积函数具有单调性，我们可以使用二分搜索来找到使上下面积相等的临界点。

  5. 坐标离散化：由于坐标范围很大，需要对y坐标进行离散化处理，只考虑正方形的上下边界作为候选分割线位置。

算法的核心是维护一个能够高效计算区间并集面积的数据结构，然后枚举所有关键的y坐标进行计算。

代码实现

class Solution {
public:
    double separateSquares(vector<vector<int>>& squares) {
        set<long long> yCoords;
        
        // 收集所有关键的y坐标
        for (auto& sq : squares) {
            yCoords.insert(sq[1]);
            yCoords.insert(sq[1] + sq[2]);
        }
        
        vector<long long> ys(yCoords.begin(), yCoords.end());
        
        // 二分搜索找到平衡点
        double left = *ys.begin(), right = *ys.rbegin();
        
        for (int iter = 0; iter < 100; iter++) {
            double mid = (left + right) / 2;
            long long aboveArea = getArea(squares, mid, true);
            long long belowArea = getArea(squares, mid, false);
            
            if (aboveArea > belowArea) {
                left = mid;
            } else {
                right = mid;
            }
        }
        
        return (left + right) / 2;
    }
    
private:
    long long getArea(vector<vector<int>>& squares, double y, bool above) {
        vector<pair<long long, long long>> intervals;
        
        for (auto& sq : squares) {
            long long x = sq[0], bottom = sq[1], side = sq[2];
            long long top = bottom + side, right = x + side;
            
            if (above) {
                if (top > y && bottom < y) {
                    // 正方形跨越分割线，取上半部分
                    intervals.push_back({x, right});
                } else if (bottom >= y) {
                    // 完全在上方
                    intervals.push_back({x, right});
                }
            } else {
                if (top > y && bottom < y) {
                    // 正方形跨越分割线，取下半部分
                    intervals.push_back({x, right});
                } else if (top <= y) {
                    // 完全在下方
                    intervals.push_back({x, right});
                }
            }
        }
        
        return mergeIntervals(intervals);
    }
    
    long long mergeIntervals(vector<pair<long long, long long>>& intervals) {
        if (intervals.empty()) return 0;
        
        sort(intervals.begin(), intervals.end());
        long long totalLength = 0;
        long long currentStart = intervals[0].first;
        long long currentEnd = intervals[0].second;
        
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i].first <= currentEnd) {
                currentEnd = max(currentEnd, intervals[i].second);
            } else {
                totalLength += currentEnd - currentStart;
                currentStart = intervals[i].first;
                currentEnd = intervals[i].second;
            }
        }
        totalLength += currentEnd - currentStart;
        
        return totalLength;
    }
};

class Solution:
    def separateSquares(self, squares: List[List[int]]) -> float:
        def merge_intervals(intervals):
            if not intervals:
                return 0
            intervals.sort()
            total_length = 0
            current_start, current_end = intervals[0]
            
            for start, end in intervals[1:]:
                if start <= current_end:
                    current_end = max(current_end, end)
                else:
                    total_length += current_end - current_start
                    current_start, current_end = start, end
            
            total_length += current_end - current_start
            return total_length
        
        def get_area(y, above):
            intervals = []
            
            for x, bottom, side in squares:
                top = bottom + side
                right = x + side
                
                if above:
                    if top > y >= bottom:
                        intervals.append((x, right))
                    elif bottom >= y:
                        intervals.append((x, right))
                else:
                    if top > y >= bottom:
                        intervals.append((x, right))
                    elif top <= y:
                        intervals.append((x, right))
            
            return merge_intervals(intervals)
        
        # 收集关键y坐标
        y_coords = set()
        for x, y, side in squares:
            y_coords.add(y)
            y_coords.add(y + side)
        
        y_coords = sorted(y_coords)
        
        # 二分搜索
        left, right = y_coords[0], y_coords[-1]
        
        for _ in range(100):
            mid = (left + right) / 2
            above_area = get_area(mid, True)
            below_area = get_area(mid, False)
            
            if above_area > below_area:
                left = mid
            else:
                right = mid
        
        return (left + right) / 2

public class Solution {
    public double SeparateSquares(int[][] squares) {
        var yCoords = new SortedSet<long>();
        
        foreach (var sq in squares) {
            yCoords.Add(sq[1]);
            yCoords.Add(sq[1] + sq[2]);
        }
        
        double left = yCoords.Min, right = yCoords.Max;
        
        for (int iter = 0; iter < 100; iter++) {
            double mid = (left + right) / 2;
            long aboveArea = GetArea(squares, mid, true);
            long belowArea = GetArea(squares, mid, false);
            
            if (aboveArea > belowArea) {
                left = mid;
            } else {
                right = mid;
            }
        }
        
        return (left + right) / 2;
    }
    
    private long GetArea(int[][] squares, double y, bool above) {
        var intervals = new List<(long, long)>();
        
        foreach (var sq in squares) {
            long x = sq[0], bottom = sq[1], side = sq[2];
            long top = bottom + side, right = x + side;
            
            if (above) {
                if (top > y && bottom < y) {
                    intervals.Add((x, right));
                } else if (bottom >= y) {
                    intervals.Add((x, right));
                }
            } else {
                if (top > y && bottom < y) {
                    intervals.Add((x, right));
                } else if (top <= y) {
                    intervals.Add((x, right));
                }
            }
        }
        
        return MergeIntervals(intervals);
    }
    
    private long MergeIntervals(List<(long, long)> intervals) {
        if (intervals.Count == 0) return 0;
        
        intervals.Sort();
        long totalLength = 0;
        long currentStart = intervals[0].Item1;
        long currentEnd = intervals[0].Item2;
        
        for (int i = 1; i < intervals.Count; i++) {
            if (intervals[i].Item1 <= currentEnd) {
                currentEnd = Math.Max(currentEnd, intervals[i].Item2);
            } else {
                totalLength += currentEnd - currentStart;
                currentStart = intervals[i].Item1;
                currentEnd = intervals[i].Item2;
            }
        }
        totalLength += currentEnd - currentStart;
        
        return totalLength;
    }
}

var separateSquares = function(squares) {
    // Get all critical y-coordinates
    const yCoords = new Set();
    for (const [x, y, l] of squares) {
        yCoords.add(y);
        yCoords.add(y + l);
    }
    
    const sortedY = Array.from(yCoords).sort((a, b) => a - b);
    
    // Function to calculate area below a given y-line
    function getAreaBelow(yLine) {
        const intervals = [];
        
        for (const [x, y, l] of squares) {
            const top = y + l;
            if (y < yLine) {
                const bottom = y;
                const actualTop = Math.min(top, yLine);
                if (actualTop > bottom) {
                    intervals.push([x, x + l, actualTop - bottom]);
                }
            }
        }
        
        return mergeIntervals(intervals);
    }
    
    // Function to merge overlapping intervals and calculate total area
    function mergeIntervals(intervals) {
        if (intervals.length === 0) return 0;
        
        // Group by height and merge x-intervals
        const heightMap = new Map();
        for (const [x1, x2, h] of intervals) {
            if (!heightMap.has(h)) {
                heightMap.set(h, []);
            }
            heightMap.get(h).push([x1, x2]);
        }
        
        let totalArea = 0;
        for (const [height, xIntervals] of heightMap) {
            xIntervals.sort((a, b) => a[0] - b[0]);
            
            let mergedLength = 0;
            let currentStart = xIntervals[0][0];
            let currentEnd = xIntervals[0][1];
            
            for (let i = 1; i < xIntervals.length; i++) {
                const [start, end] = xIntervals[i];
                if (start <= currentEnd) {
                    currentEnd = Math.max(currentEnd, end);
                } else {
                    mergedLength += currentEnd - currentStart;
                    currentStart = start;
                    currentEnd = end;
                }
            }
            mergedLength += currentEnd - currentStart;
            
            totalArea += mergedLength * height;
        }
        
        return totalArea;
    }
    
    // Calculate total area
    const totalArea = getAreaBelow(Math.max(...sortedY));
    const targetArea = totalArea / 2;
    
    // Binary search for the answer
    let left = 0, right = sortedY.length - 1;
    
    while (right - left > 1) {
        const mid = Math.floor((left + right) / 2);
        const area = getAreaBelow(sortedY[mid]);
        
        if (area <= targetArea) {
            left = mid;
        } else {
            right = mid;
        }
    }
    
    // Check if exact match at a critical point
    const areaAtLeft = getAreaBelow(sortedY[left]);
    const areaAtRight = getAreaBelow(sortedY[right]);
    
    if (Math.abs(areaAtLeft - targetArea) < 1e-9) {
        return sortedY[left];
    }
    if (Math.abs(areaAtRight - targetArea) < 1e-9) {
        return sortedY[right];
    }
    
    // Linear interpolation between the two points
    const y1 = sortedY[left];
    const y2 = sortedY[right];
    const area1 = areaAtLeft;
    const area2 = areaAtRight;
    
    if (Math.abs(area2 - area1) < 1e-9) {
        return y1;
    }
    
    const result = y1 + (targetArea - area1) * (y2 - y1) / (area2 - area1);
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n² log n)
空间复杂度O(n)

其中 n 是正方形的数量。时间复杂度主要来自二分搜索的迭代次数（常数次）乘以每次计算面积时的区间合并操作。

相关题目