[poj 2482] Stars in Your Window
2021-05-03 06:27
阅读：540
这封情书。。。写的可真有水平啊。。值得借鉴qwq
好吧，这其实就是非常经典的扫描线题。
这种题目，我们先需要转换一下。
题目中用矩形框点，可以等价变换为求以每个点为角（任意一个）的矩形的最大交。
这样，我们相当于把原问题变成了求出矩形面积并，只是另类一点而已（还简单了不少）。
那么，我们可以用一个差分的思想，将一个点(x,y,z)的信息先转为一个矩形(x,y,W,H,z)，再变成两条线段。
这两条线段的信息分别为(y,x,x+W,z)和(y+H,x,x+W,-z)。
其中值得注意的是，题目中说了，不包含边界上面的点，所以上方的两条线段实际上只包含左端点而不包含右端点。
然后这就变成了加权线段覆盖问题。完全就是线段树的范围。
但是我们还要先按x坐标离散一下，再建立，更新线段树。
当然还要注意，我们更新线段树要有顺序，比如从上往下或从下往上都可以。
但还要注意的是，只有当你把同一高度的线段都处理完了，才能进行查询，更新答案，否则可能会导致负标记还没删完，答案就更新了。
下一篇：win32 api 文件处理
文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：[poj 2482] Stars in Your Window
文章链接：http://soscw.com/index.php/essay/81676.html
文章标题：[poj 2482] Stars in Your Window
文章链接：http://soscw.com/index.php/essay/81676.html
评论
亲，登录后才可以留言！