[問題] 繩子圍石頭

[obelisk0114 (追風箏的孩子)]

之前看到一題十分困難的題目,大致長這樣:

平面上有許多點,要用一條固定長度的繩子圈住最多點

繩子需要頭尾相連

由於題目並未提到其他限制,所以任意形狀的圈法都可以

目前只有想到用凸多邊形去圍

但是實際做法沒有頭緒

各位大大有何想法 ?

--
    肝不好           ▁▁        ●       ◤            肝若好
        人生是黑白的     ▏             ◤                   考卷是空白的
                         ▏           ◤                  、 ﹐
  ●      ●b     囧     ▎  ●> ● ◤  ▌ ﹍﹍ ０      ▊囧＞ 幹...
  ▲      ■┘    ■     ▎  ■ █◤    ▌      ㄏ▋     ︶■
 〈﹀     ∥  ▁▁∥     ▎ ﹀〉◤      ▋        ▊      〈\  ψcockroach727

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 47.149.227.123
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1511004973.A.C35.html
推 DJWS: 換句話說就是找「剛好包含k個點、周長最短的凸多邊形」
→ DJWS: https://stackoverflow.com/questions/3087372/
→ DJWS: 用上面網頁的做法  然後窮舉試誤or二分搜尋k是多少