Re: [問題] 繩子圍石頭
看板Prob_Solve (計算數學 Problem Solving)作者iago2007 (柔)時間7年前 (2017/12/10 15:43)推噓1(1推 0噓 0→)留言1則, 1人參與討論串3/3 (看更多)
反例:
四個點分別為
A (-0.9,0)
B (0,0)
C (sqrt(3)/2,1/2)
D (sqrt(3)/2,-1/2)
給定長度1.8的繩子，理論上要圍出AB兩點
不過按照這個方法會找到BCD之後發現任兩點周長都是2而找不到兩點的圍法。
本質在於圍兩點的最小圍法(AB)並不包含於圍三點的最小圍法(BCD)當中
※ 引述《cocoyan (摳摳厭)》之銘言：
: ※ 引述《obelisk0114 (追風箏的孩子)》之銘言：
: : 之前看到一題十分困難的題目,大致長這樣:
: : 平面上有許多點,要用一條固定長度的繩子圈住最多點
: : 繩子需要頭尾相連
: : 由於題目並未提到其他限制,所以任意形狀的圈法都可以
: : 目前只有想到用凸多邊形去圍
: : 但是實際做法沒有頭緒
: : 各位大大有何想法 ?
: 先把所有點用一個凸多邊形包住
: 凸多邊形的每一個角都至少代表一個點
: 由於三角形的兩邊長必大於第三邊
: 所以拿掉其中一個角後
: 再用新的凸多邊形把剩下來的點包住
: 新凸多邊形的周長會小於或等於原本的周長
: 每次都拿掉周長能夠減少最多的那個點
: 直到周長小於或等於繩子的長度
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.160.94.230
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1512891798.A.ACE.html
※ 編輯: iago2007 (118.160.84.116), 01/03/2018 13:57:45
推
01/27 15:01,
7年前
, 1F
01/27 15:01, 1F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
