hdu 3642 Get The Treasury (线段树+扫描线,求长方体体积交)

hdu3642题目链接

题意:给出若干个(1000)长方体,求至少交三次的空间的体积。

尺寸为[x1,x2],[y1,y2],[z1,z2],其中x,y的坐标的绝对值不超过1E6,Z的坐标的绝对值不超过1E9.

思路:

线段树+扫描线。

由于Z的坐标范围比较小,我们的做法是 利用“微分”的思想,将每个长方体,想成若干的高度为1的矩形(矩形片)

因此就转化成了求矩形至少交三次的面积

其中和矩形交,也就是矩形至少交2次的面积比较类似,只不过线段树多维护一个至少三次覆盖的长度的域。

 

假设我们有一个长为5,宽为6,高为7的长方体

那么我们就要将其拆成7个,长为5,宽为6的矩形

将所有长方体处理完之后,枚举高度,对于每一个高度,如果矩形大于等于三个,就做一个“矩形的三次面积交”操作,将答案累加。

2A,PushUp的时候写错了一句。。。即如果父亲节点已经覆盖了两次,那么父亲节点被覆盖三次的是从左右儿子被覆盖一次的情况得来的

 

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz