Posted on 2010-03-03 15:29
王之昊 阅读(158)
评论(0) 编辑 收藏 引用 所属分类:
pku
题目大意是有若干个大小不一（整数）的正方形，从左到右呈45`放置。相互紧靠，问从正上方能看到的正方形有哪些。最多50个正方形。
如果能确定每个正方形的位置。那么就可以很轻松的算出遮挡关系。这可以转换成一些区间的覆盖问题。
如果确定了1,2,...，k-1的位置，现在要确定第 k 个的位置。假设有两个正方形a，b。a的位置已经确定为 Xa，b在a的右边，那么 Xb = Xa + min(a, b)*sqrt(2);这样就可以确定第k块正方形的位置了。
注意到上面涉及浮点数，我们把边长扩大根号二倍，不影响最后结果，但只有整数间的运算。