討論串[請益] Largest Empty Circle(LEC) Problem
共 5 篇文章
內容預覽:
2010/12/11 首po. 想請教Largest Empty Circle(LEC) Problem在O(NlogN)算法的實作步驟。. 何謂LEC Problem？. 平面上一個矩形區域裡有N個點。. 找區域裡的一個最大圓，圓內不得包含任意一個點(圓邊上可以)。. 目前的努力：. 因為是最大圓
(還有430個字)
內容預覽:
一條邊的中垂線上任何一點，都與兩個頂點距離相等，. 三角形的外心則是三邊中垂線的交點，同時也是外接圓的圓心，. 自然和三角形頂點距離都相同。. 跟 convex null 似乎倒是沒什麼關係，. 而且很容易可以找到一個反例，. 想像一個 convex hull 中間密密麻麻塞滿了點，只有中心位置有一
(還有505個字)
內容預覽:
感謝您的回應，. 然而，我的原文指的是convex hull任意不照順序的三點所構成三角形，. (我原文少講了任意，造成你的誤解真抱歉). 這個三角形的外心有可能落在你講的中心位置。. 其實這也是一個題目，SPOJ34或POJ1379。. 原本我已實作出O(N^4)的代碼，我用假設的方式，. 將co
(還有161個字)
內容預覽:
呃不知道我有沒有誤會你的意思... 那例如底下的測資，4個點:. (-4,-3) (4,-3) (0,5) (0,0). 那convex hull是前三個點，這也是唯一的三角形取法. 不過它的圓心在 (0,0) 這顯然不是最大空圓的圓心. 這題的測資大小，看起來是O(N^2lgN)就夠了. 方法是枚
(還有316個字)
內容預覽:
結論應該是：只用convex hull來計算LEC的圓心是錯的。. 我發現程式跑上述資料因為利用三角形三頂點求出的(0,0). 恰與測資點(0, 0)重合，就被剔除掉了。. 所以這個階段跑不出結果。. 但後續的動作跑出的結果彌補了這個缺失，. 所以答案會和judge系統上的一樣。. 附帶一提，SPO
(還有222個字)