矩形的面积并问题:平面上有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*纵坐标之差就是竖直线段的长度。


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理