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