首页 > Atlantis
开通博客写题解
头像 威风镰鼬
发表于 2021-08-17 17:26:28
思路 这道题是扫描线线段树的板子题，具体的处理方法：(1)每个矩形的上下边加入扫描线并标记，下边标记为1，上边标记为-1(2)让扫描线从从低到高排序，而矩形的左右边从小到大排序(3)考虑数据范围，我们进行离散化处理(3)建立线段树，那么区间可表示为区域的y1,y2，以及长度。(4)遍历所有相邻左右边 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 louhc
发表于 2019-08-20 17:50:36
(话说这篇题解我在洛谷发过,所以图有水印...) 思路 扫描线经典题.图1我们从左到右扫描所有的纵向边. 图2 - 红色边即为依次扫描到的边. 这些边可以用一个结构体记录.需要记录横坐标,上下边界(纵坐标),是一个矩形的结束还是开始.扫描这些边时,我们用数据结构维护每个位置纵坐标被矩形覆盖了多少.如 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”