回 帖 发 新 帖 刷新版面

主题:[讨论]仓库扩张(USACO Contest DEC05) 50分悬赏

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

回复列表 (共1个回复)

沙发

用并查集。。。把每个矩形块当成一个点,两个矩形块相交代表这两个点有连线。接下来扫一遍即可。

话说高三时间真少啊。。

我来回复

您尚未登录,请登录后再回复。点此登录或注册