Re: [問題] 繩子圍石頭
看板Prob_Solve (計算數學 Problem Solving)作者cocoyan (摳摳厭)時間7年前 (2017/12/09 18:11)推噓0(0推 0噓 0→)留言0則, 0人參與討論串2/3 (看更多)
※ 引述《obelisk0114 (追風箏的孩子)》之銘言：
: 之前看到一題十分困難的題目,大致長這樣:
: 平面上有許多點,要用一條固定長度的繩子圈住最多點
: 繩子需要頭尾相連
: 由於題目並未提到其他限制,所以任意形狀的圈法都可以
: 目前只有想到用凸多邊形去圍
: 但是實際做法沒有頭緒
: 各位大大有何想法 ?
先把所有點用一個凸多邊形包住
凸多邊形的每一個角都至少代表一個點
由於三角形的兩邊長必大於第三邊
所以拿掉其中一個角後
再用新的凸多邊形把剩下來的點包住
新凸多邊形的周長會小於或等於原本的周長
每次都拿掉周長能夠減少最多的那個點
直到周長小於或等於繩子的長度
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.24.19.70
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1512814263.A.C02.html
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
