PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [請益] Largest Empty Circle(LEC) Problem

看板Prob_Solve (計算數學 Problem Solving)作者bleed1979 (十三)時間14年前 (2010/12/12 06:42)推噓2(2推 0噓 3→)

留言5則, 2人參與討論串5/5 (看更多)

※ 引述《seanwu (海恩)》之銘言： : 呃不知道我有沒有誤會你的意思... 那例如底下的測資，4個點: : (-4,-3) (4,-3) (0,5) (0,0) : 那convex hull是前三個點，這也是唯一的三角形取法 : 不過它的圓心在 (0,0) 這顯然不是最大空圓的圓心結論應該是：只用convex hull來計算LEC的圓心是錯的。我發現程式跑上述資料因為利用三角形三頂點求出的(0,0) 恰與測資點(0, 0)重合，就被剔除掉了。所以這個階段跑不出結果。但後續的動作跑出的結果彌補了這個缺失，所以答案會和judge系統上的一樣。附帶一提，SPOJ34這題是尋找矩形上或矩形內離測資點為最遠距離的點，就變成即使求出了LEC的圓心，還是要考慮矩形上的可能。我的程式也做了後半段，才造成幸運的結果。但是如果只是求LEC的圓心，就不能只用convex hull的方式去做。 : : 其實這也是一個題目，SPOJ34或POJ1379。 : : 原本我已實作出O(N^4)的代碼，我用假設的方式， : : 將convex hull的所有點數當成"新的N"套入這個O(N^4)的算法。 : : 再計算矩形4個角，矩形4個邊的其中一個邊上所有點，矩形中心點， : : 總共這麼多的運算，幸運地AC了。 : : 關鍵應該是原本的N至多1000點，跑O(N^4)很慢。 : : 但是我把convex hull的總點數來跑O(N^4)就很快了， : : 以上提供給需要解題的人。 : 這題的測資大小，看起來是O(N^2lgN)就夠了 : 方法是枚舉每個點p，求p對其它所有點連線段的中垂線的半平面交集 : N條直線的半平面交可以O(NlgN)做完，而可能的LEC圓心則必在半平面交的頂點上 : (其實這個就是Voronoi了，不過比較好做一點，當然時間複雜度也比較差一點) 我有找到利用C++的deque做半平面交的文章，題目也類似於POJ2451(不過這題是求面積)，但是對於大前題我就有點疑問了，疑問就是如何知道中垂線所分成的的半平面是 >= 0 還是 <= 0 如果在不確定的情況下可以直接計算嗎？(還沒開始動手) 因為POJ2451這題所給的線段已經確定全部都是 >= 0 了。 : : 結果我還是沒有實作出O(NlogN)的算法，sigh... : 這個超級不好寫噢XDD : 有興趣可以看一下這個 : http://oistorer.blogspot.com/2006/08/2006_15.html : 裡面有一篇《浅析平面Voronoi图的构造及应用》 : 提到了做法和一些應用 : 它用的是divide&conquer的方法，對於兩個不相交各N/2個點的triangulation : 我們有(說來容易的)方法可以在O(N)的時間合併它們 : 不過要真的寫到O(NlogN)的話就.. 有點不太健康嗯，我有空請簡體書店訂這本，不過很怕以我的水準會看不懂。 Bleed -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.43.124.23