哎哟 我肏
这题怎么这么难, 写到现在 干干干
3454. Separate Squares II
跟昨天不同, 今天的题目, 重叠的面积只能算一次
思路 :
用segment tree纪录目前x轴累积的宽度
首先把每个正方形拆成两个平行x轴的边称为上边、下边
并且以[x1,x2,y,k]的形式记录起来, 其中k是用来记录这是上边还是下边
并且依照y的大小排序
当遇到下边时, 要把下边这段长度(x2-x1)加到累积宽度里
反之遇到上边, 要把上边的长度扣掉
就这样遍历所有边
每次都将 累积的宽度*(目前边的y-上一条边的y) 加到面积里
算出总面积后
再从头算一次
这次算到面积 >= 总面积的一半后
将 目前的y - ( 目前的面积 - 总面积的一半后 ) / 累积宽度就是答案
golang code :
type Node struct {
l, r int
k int
length int
}
type SegmentTree struct {
nums []int
tree []Node
}
func newTree(nums []int) *SegmentTree {
n := len(nums)
t := make([]Node, 4*n)
s := &SegmentTree{
nums: nums,
tree: t,
}
s.build(0, 0, n-1)
return s
}
func (t *SegmentTree) build(u, l, r int) {
t.tree[u].l = l
t.tree[u].r = r
if l != r {
mid := l + (r-l)/2
t.build(u*2+1, l, mid)
t.build(u*2+2, mid+1, r)
}
}
func (t *SegmentTree) modify(u, l, r, k int) {
if t.tree[u].l > r || t.tree[u].r < l {
return
}
if l <= t.tree[u].l && t.tree[u].r <= r {
t.tree[u].k += k
} else {
mid := t.tree[u].l + (t.tree[u].r-t.tree[u].l)/2
if l <= mid {
t.modify(u*2+1, l, r, k)
}
if r > mid {
t.modify(u*2+2, l, r, k)
}
}
if t.tree[u].k > 0 {
t.tree[u].length =
t.nums[t.tree[u].r+1] - t.nums[t.tree[u].l]
} else if t.tree[u].l == t.tree[u].r {
t.tree[u].length = 0
} else {
t.tree[u].length = t.tree[u*2+1].length + t.tree[u*2+2].length
}
}
func (t *SegmentTree) query() int {
return t.tree[0].length
}
func separateSquares(squares [][]int) float64 {
n := len(squares)
events := make([][]int, 0, 2*n)
xs := make([]int, 0)
recX := make(map[int]bool)
for i := 0; i < n; i++ {
x1, y1, l := squares[i][0], squares[i][1], squares[i][2]
x2, y2 := x1+l, y1+l
events = append(events, []int{x1, x2, y1, 1})
events = append(events, []int{x1, x2, y2, -1})
if !recX[x1] {
recX[x1] = true
xs = append(xs, x1)
}
if !recX[x2] {
recX[x2] = true
xs = append(xs, x2)
}
}
slices.Sort(xs)
slices.SortFunc(events, func(a, b []int) int {
return a[2] - b[2]
})
st := newTree(xs)
area, y0 := 0.0, 0
posX := make(map[int]int)
for i, val := range xs {
posX[val] = i
}
for _, event := range events {
x1, x2, y, k := event[0], event[1], event[2], event[3]
width := st.query()
area += float64((y - y0) * width)
st.modify(0, posX[x1], posX[x2]-1, k)
y0 = y
}
target := area / 2.0
area = 0.0
for _, event := range events {
x1, x2, y, k := event[0], event[1], event[2], event[3]
width := st.query()
area += float64((y - y0) * width)
st.modify(0, posX[x1], posX[x2]-1, k)
if area >= target {
return float64(y) - (area-target)/float64(width)
}
y0 = y
}
return 0.0
}