Posted on 2010-03-03 15:29
王之昊 閱讀(183)
評論(0) 編輯 收藏 引用 所屬分類:
pku
題目大意是有若干個大小不一（整數）的正方形，從左到右呈45`放置。相互緊靠，問從正上方能看到的正方形有哪些。最多50個正方形。
如果能確定每個正方形的位置。那么就可以很輕松的算出遮擋關系。這可以轉換成一些區間的覆蓋問題。
如果確定了1,2,...，k-1的位置，現在要確定第 k 個的位置。假設有兩個正方形a，b。a的位置已經確定為 Xa，b在a的右邊，那么 Xb = Xa + min(a, b)*sqrt(2);這樣就可以確定第k塊正方形的位置了。
注意到上面涉及浮點數，我們把邊長擴大根號二倍，不影響最后結果，但只有整數間的運算。