Posted on 2011-07-02 11:17
Mato_No1 阅读(2739)
评论(0) 编辑 收藏 引用 所属分类:
线段树
矩形的面积并问题：平面上有N个矩形，各边均平行于坐标轴，求它们覆盖的总面积（重复覆盖的只计一次）。
矩形的周长并问题：平面上有N个矩形，各边均平行于坐标轴，求它们覆盖形成的多边形的周长。
【算法】
面积并：
先将所有矩形的上边界和下边界作为水平线段记录下来，并对所有矩形的左右边界对应的横坐标离散化，设离散化后有N个横坐标，则中间有(N-1)段。对这(N-1)段建立线段树（注意，仍然和普通线段树一样，是双闭区间，不是网上说的一开一闭），然后，按照纵坐标递增顺序扫描前面记录的水平线段（设有M段），对每一段，如果是上边界，找到其离散化后的范围（只需找到其左右端点离散化后的值l、r，则对应范围为[l, r-1]），并插入线段[l, r-1]，否则（下边界），删除线段[l, r-1]。再然后，线段树中的每个结点需要记录该区间内的线段覆盖的总长度len（若该区间被某条尚未删除的线段整体覆盖，则len=总长，否则len=左右子结点len之和），每次操作后，累加面积：T[root].len*该水平线段与下一条水平线段的纵坐标之差。
周长并：
类似，只不过由于组成周长的线段有水平的也有竖直的，线段树结点要记录的除了len意外还有一个ss，表示被线段覆盖的端点数量。另外还有lr和rr两个bool值，分别表示该线段的左端点和右端点是否被某条插入的线段覆盖。则T[x].ss = lch(T[x]).ss + rch(T[x]).ss - 2 * (lch(T[x]).rr && rch(T[x].lr))，若该线段被整体覆盖则T[x].ss=2（两端点）。最后，这次得到的T[root].len与上次得到的T[root].len之差的绝对值就是水平线段的长度，T[root].ss*纵坐标之差就是竖直线段的长度。