TA貢獻1876條經(jīng)驗 獲得超6個贊
題主請速看你的評論。這個問題和POJ2482是完全等同的，你可以去直接查找解題報告。樸素遍歷我覺得達不到O(n^2)的復雜度，因為你不能假定任何一個目標都在矩形的角點上。事實上POJ給出的范圍n<=10000就是照著O(n^2)或接近的復雜度來的，絕對不是要求在O(nlogn)左右解決。例如四個點如果在(0,1)(0,-1)(-1,0)(1,0)，目標區(qū)域為2*2，則此時最優(yōu)解為4。但如果把任何一個目標當作角點，無論向哪個方向擴展，都會得到錯解3。你可以畫一畫這個圖，非常顯然。遍歷是跑不了的，不過誰說遍歷非要O(n^2)呢？對于線段的區(qū)間查詢用線段樹，對于矩形的子矩形查詢用二維線段樹。預處理離散化處理。先只審查X坐標。把所有點的X坐標排序，形成有序列表X[0]...X[i]，O(nlogn)。記錄每個X[i]到最近的下一個X坐標X[i+1]的距離。相同就記0，沒關系。掃描從每個X[i]開始，向右延伸h的距離，最遠能覆蓋到的坐標位置k（即max(k)within{k>iandX[k]<=X[i]+h}）。注意用左右雙下標線性前推，這個掃描是O(n)的可不是O(n^2)。對Y坐標重復以上的步驟。最后將X和Y軸，都歸約成[0,1,...,n-1]這樣的元素數(shù)量為n的線性整數(shù)區(qū)間。至于各個點之間的X、Y軸距離，被記錄到了每個點的權值，成為了一種附加數(shù)據(jù)。線段樹和二維線段樹線段樹就是把區(qū)間不斷二分形成一個二叉樹。每一個節(jié)點代表一個區(qū)間，左子樹和右子樹，是將這個區(qū)間一分為二的結果，合并起來等同于父親節(jié)點的區(qū)間。在線段樹上，查詢?nèi)我庖粋€區(qū)間，都是最優(yōu)O(logn)的。離散化處理的意義就在于，忽略一切坐標之間長長短短的差異，將坐標“平均化”成若干個元素。這樣在建樹的時候，就可以完全避免不平衡狀況，不會造成二叉樹查詢的退化，時間復雜度保證最優(yōu)。只要分開審查X和Y兩個維度，就可以把線段樹擴展到二維。二維線段樹的簡單想法，就是二叉樹套二叉樹。用線段樹負責一個維度，線段樹的每一個節(jié)點里再建立一個二叉樹，負責另一個維度。這樣查詢?nèi)我庖粋€矩形范圍，都是O(logn*logn)的。剩下的算法就略了，二維線段樹的算法是現(xiàn)成的。如果我沒弄錯，那么總體復雜度是O(n^2*(logn)^2)的，感謝評論指正。
TA貢獻1810條經(jīng)驗 獲得超4個贊
很感謝@沙渺和ZhenboLi提供的思路。搜索"poj2482"或者"starsinyourwindow"的確有解決的辦法。其實我的原意是要解決一個裁切圖片的問題，我的圖片經(jīng)過OpenSURF算法能夠得到一組特征坐標的數(shù)組（特征點沒有權值），接下來就要截取一個矩形區(qū)域，這個區(qū)域應該覆蓋盡可能多的特征點。后來轉(zhuǎn)換了一下思路，其實妥協(xié)一下就能很簡單地解決這個問題，我把圖片resize為和矩形區(qū)域一樣的寬度或者高度，再去獲取特征坐標，接下來就只剩求一個維度的上的最大區(qū)間問題了。
舉報