| ||||||||||
Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
题解 举行面积求并 离散化题目大意:给定每个矩形的对角线的两个端点,让你求这些矩形的面积的并集,即重叠的不能重复计算 题目分析:这题就是典型的线段树求面积并 离散化:对所有节点的Y进行升序排序,然后以Y的位置建树,就是指,在线段树里面,左右节点的实际意义就是指这个线段在Y的升序数组里的位置,但是我们把lf,rf赋值为这个线段左右端点的具体值,这就是离散化 建树的细节:树的每个节点有lf,rf,cover,lenth,分别指这个节点所表示的线段的左端点,右端点,被覆盖的次数(在这里覆盖的次数是为了区分重叠矩形的情况下,高度的正确存取,因为一个矩形对Y轴的覆盖是以他的左边开始,右边结束的,所以当插入左边的时候,我们把cover+1,右边的时候把cover-1,说明这个矩形对Y的覆盖已经结束,计算下一个矩形时,不会错误的把我这个矩形的高度当作下一个矩形的高度),lenth指这个区间被矩形覆盖的长度即矩形的实际高度;插入的时候,先把存放节点的数组,对X进行升序排序,然后顺次插入,分别计算 http://blog.csdn.net/u011328276/article/details/9496999 Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator