3454：分割正方形 II（2671 分）

Ian

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

力扣第 150 场双周赛第 3 题

题目

给你一个二维整数数组 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.00000

解释：

由于蓝色正方形和红色正方形有重叠区域且重叠区域只统计一次。所以直线 y = 1 将正方形分割成两部分且面积相等。

提示：

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¹⁵。

相似问题：

0850：矩形面积 II（2235 分）

分析

#1

3453 进阶版，同样可以采用扫描线的方法
区别在于重叠区域只算一次，需要用数据结构维护扫描时的区域大小
这个问题类似 0850，可以用有序集合维护

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


from sortedcontainers import SortedList
class Solution:
    def separateSquares(self, squares: List[List[int]]) -> float:
        def cal(sl):
            res,e = 0,0
            for l,r in sl:
                if r>e:
                    res += r-max(l,e)
                    e = r
            return res
        d = defaultdict(list)
        for x,y,l in squares:
            d[y].append((1,x,x+l))
            d[y+l].append((0,x,x+l))
        s = 0
        sl = SortedList()
        for y1,y2 in pairwise(sorted(d)):
            for flag,x1,x2 in d[y1]:
                if flag:
                    sl.add((x1,x2))
                else:
                    sl.remove((x1,x2))
            s += cal(sl)*(y2-y1)
        t = 0
        sl = SortedList()
        for y1,y2 in pairwise(sorted(d)):
            for flag,x1,x2 in d[y1]:
                if flag:
                    sl.add((x1,x2))
                else:
                    sl.remove((x1,x2))
            w = cal(sl)
            t += w*(y2-y1)
            if t*2>=s:
                return y2-(t*2-s)/2/w

808 ms

#2

也可以用线段树维护，时间复杂度更优

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71


class Seg:
    def __init__(self,n):
        self.L = n.bit_length()
        self.N = N = 1<<self.L
        self.t = [0]*N*2
        self.f = [0]*N*2
        self.sz = [0]*N*2
        
    def apply(self,o,x):            
        self.t[o] += x
        self.f[o] += x

    def build(self,A):
        for i in range(len(A)-1):
            self.sz[self.N+i] = A[i+1]-A[i]
        for o in range(self.N-1,0,-1):
            self.pull(o)

    def pull(self,o):
        t,sz = self.t,self.sz
        t[o] = min(t[o*2],t[o*2+1])
        sz[o] = sz[o*2]*(t[o]==t[o*2])+sz[o*2+1]*(t[o]==t[o*2+1])

    def push(self,o):
        if self.f[o] != self.f[0]:
            self.apply(o*2,self.f[o])
            self.apply(o*2+1,self.f[o])
            self.f[o] = self.f[0]

    def modify(self,a,b,x):
        a,b = a+self.N-1,b+self.N+1  
        for i in range(self.L,0,-1):  
            self.push(a>>i)  
            self.push(b>>i)  
        while a^b^1:  
            if not a&1: self.apply(a^1,x)  
            if b&1: self.apply(b^1,x)  
            a,b = a>>1,b>>1  
            self.pull(a)  
            self.pull(b)  
        while a>>1:
            a >>= 1
            self.pull(a)

class Solution:
    def separateSquares(self, squares: List[List[int]]) -> float:
        V = sorted({a for x,y,l in squares for a in [x,x+l]})
        mp = {a:i for i,a in enumerate(V)}
        d = defaultdict(list)
        for x,y,l in squares:
            x1,x2 = mp[x],mp[x+l]-1
            d[y].append((x1,x2,1))
            d[y+l].append((x1,x2,-1))
        s = 0
        seg = Seg(len(V)-1)
        seg.build(V)
        for y1,y2 in pairwise(sorted(d)):
            for x1,x2,flag in d[y1]:
                seg.modify(x1,x2,flag)
            w = V[-1]-V[0]-(seg.sz[1] if seg.t[1]==0 else 0)
            s += w*(y2-y1)
        t = 0
        seg = Seg(len(V)-1)
        seg.build(V)
        for y1,y2 in pairwise(sorted(d)):
            for x1,x2,flag in d[y1]:
                seg.modify(x1,x2,flag)
            w = V[-1]-V[0]-(seg.sz[1] if seg.t[1]==0 else 0)
            t += w*(y2-y1)
            if t*2>=s:
                return y2-(t*2-s)/2/w

4765 ms

目录

3454：分割正方形 II（2671 分）

题目

分析

#1

#2

解答