Poj2482 Stars in Your Window（扫描线）
2021-06-18 16:18
阅读：451
下面内容引用自"李煜东 《算法竞赛进阶指南》"（对原文略有缩减，侵删）：
因为矩形的大小固定，所以矩形可以由它的任意一个顶点唯一确定。我们可以考虑把矩形的右上角顶点放在什么位置，圈住的星星亮度总和最大。
所以，对于一颗星星，能够覆盖住这颗星星的右上角的位置在区间\([x,y]-[x+w,y+h]\)之间，但是由于边界上的星星不算，所以不妨将星星变为\([x-0.5,y-0.5]\)，于是右上角变为\([x+w-1,y+h-1]\)。
问题就转化成了：平面上有若干个区域，每个区域都带有一个权值，求在哪个坐标上重叠的区域权值和最大。可以用扫描线算法来解决。
具体来说，将一颗星星抽象成一个矩形，取出左右边界（四元组）：\((x,y,y+h-1,c)\)和\((x+w,y,y+h-1,-c)\)，然后按照横坐标排序。关于纵坐标建立一颗线段树，维护区间最大值\(dat\)，初始全为\(0\)，线段树上的一个值\(y\)表示区间\([y,y+1]\)，注意扫描每个四元组\((x,y_1,y_2,c)\)，执行区间修改，把\([y1,y2]\)中的每一个数都加\(c\)，用根节点\(dat\)更新就好了。
文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：Poj2482 Stars in Your Window（扫描线）
文章链接：http://soscw.com/essay/95548.html
文章标题：Poj2482 Stars in Your Window（扫描线）
文章链接：http://soscw.com/essay/95548.html
评论
亲，登录后才可以留言！