潇洒柠檬

文章
8
资源
0
加入时间
2年10月21天

hdu 3642(扫描线)

题意:有n个立方体,给出每个立方体的左下角坐标和右上角坐标,问至少三个立方体相交的体积和。 题解:刚做了一个平面的,其实原理一样,都是用线段树维护区间内不覆盖、覆盖一次、覆盖两次、覆盖三次的长度,然后区间合并仔细写就行了,因为z轴的取整范围最多到500,可以直接把所有z坐标保存排序然后枚举每小段z轴,把所有包含这段的立方体用扫描线处理,转化为平面问题,每次的计算的面积结果乘这小段z轴长度就是体积。