3453：分割正方形 I（1735 分）

Ian

2025-02-15 约 509 字预计阅读 2 分钟次阅读

力扣第 150 场双周赛第 2 题

题目

给你一个二维整数数组 squares ，其中 squares[i] = [x_i, y_i, l_i] 表示一个与 x 轴平行的正方形的左下角坐标和正方形的边长。

找到一个最小的 y 坐标，它对应一条水平线，该线需要满足它以上正方形的总面积等于该线以下正方形的总面积。

答案如果与实际答案的误差在 10^-5 以内，将视为正确答案。

注意：正方形 可能会 重叠。重叠区域应该被 多次计数 。

示例 1：

输入： squares = [[0,0,1],[2,2,1]]

输出： 1.00000

解释：

任何在 y = 1 和 y = 2 之间的水平线都会有 1 平方单位的面积在其上方，1 平方单位的面积在其下方。最小的 y 坐标是 1。

示例 2：

输入： squares = [[0,0,2],[1,1,1]]

输出： 1.16667

解释：

面积如下：

线下的面积：7/6 * 2 (红色) + 1/6 (蓝色) = 15/6 = 2.5。
线上的面积：5/6 * 2 (红色) + 5/6 (蓝色) = 15/6 = 2.5。

由于线以上和线以下的面积相等，输出为 7/6 = 1.16667。

提示：

1 <= squares.length <= 5 * 10⁴
squares[i] = [x_i, y_i, l_i]
squares[i].length == 3
0 <= x_i, y_i <= 10⁹
1 <= l_i <= 10⁹
所有正方形的总面积不超过 10¹²。

分析

扫描线累加面积，假如累加了 y1 到 y2 的面积后 t>=总面积 s/2，说明答案在 y1 和 y2 之间
设 y1 到 y2 间的单位增量为 w，所求的 y=y2-(t-s/2)/w

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution:
    def separateSquares(self, squares: List[List[int]]) -> float:
        d = defaultdict(int)
        s = 0
        for _,y,l in squares:
            d[y] += l
            d[y+l] -= l
            s += l*l
        t = 0
        l = 0
        for y1,y2 in pairwise(sorted(d)):
            l += d[y1]
            t += l*(y2-y1)
            if t*2>=s:
                return y2-(t*2-s)/l/2

257 ms

目录

3453：分割正方形 I（1735 分）

题目

分析

解答