主题:[讨论]仓库扩张(USACO Contest DEC05) 50分悬赏
仓库扩张(USACO Contest DEC05)
在FJ的农场里有N(1<=N<=25000)个长方形仓库,这些仓库的四条边都分别与x轴、y轴平行,且四角坐标均为正数,范围为0..1000000。这些仓库都不互相重叠,但是可能有一些点或者一段边是它们共有的。
一次,FJ得到了更多的奶牛去挤奶,因此他想扩张自己的仓库。一个仓库有能够扩张的条件是它不与别的仓库存在任何一个公共角或者任意一段公共边。请你计算有多少个仓库可以扩张。
[em18][em18][em18]
求解!!!(源程序)
我实在无能为力?!想了半天!
在FJ的农场里有N(1<=N<=25000)个长方形仓库,这些仓库的四条边都分别与x轴、y轴平行,且四角坐标均为正数,范围为0..1000000。这些仓库都不互相重叠,但是可能有一些点或者一段边是它们共有的。
一次,FJ得到了更多的奶牛去挤奶,因此他想扩张自己的仓库。一个仓库有能够扩张的条件是它不与别的仓库存在任何一个公共角或者任意一段公共边。请你计算有多少个仓库可以扩张。
[em18][em18][em18]
求解!!!(源程序)
我实在无能为力?!想了半天!