wcwswswws的日记

wcwswswws

sgu394

    题目意思很简单，就是在平面上有n(<=2*10^5)个匹萨店，每个匹萨店覆盖范围wi(曼哈顿距离)，若某个匹萨店被其他至少k个匹萨店覆盖则可以取消。求那些匹萨店可以被取消。

    这个问题可以被简化成一个很简单的问题：求某个点被多少个矩形覆盖。这个问题用线段树解决。

    由于每个匹萨店按照覆盖范围展开后，将边界上的点连接恰可视为一个正方形。如果我们将坐标轴旋转45度，那么这个正方形的边就平行于坐标轴。剩下的就是上面一段提到的问题了。至此这题就被ac了。

posted on 2012-01-17 01:24 世界厕所所长 阅读(189) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理