Re: [問題] 繩子圍石頭

作者: iago2007 (柔)   2017-12-10 15:43:14
反例:
四個點分別為
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 (追風箏的孩子)》之銘言:
: : 之前看到一題十分困難的題目,大致長這樣:
: : 平面上有許多點,要用一條固定長度的繩子圈住最多點
: : 繩子需要頭尾相連
: : 由於題目並未提到其他限制,所以任意形狀的圈法都可以
: : 目前只有想到用凸多邊形去圍
: : 但是實際做法沒有頭緒
: : 各位大大有何想法 ?
: 先把所有點用一個凸多邊形包住
: 凸多邊形的每一個角都至少代表一個點
: 由於三角形的兩邊長必大於第三邊
: 所以拿掉其中一個角後
: 再用新的凸多邊形把剩下來的點包住
: 新凸多邊形的周長會小於或等於原本的周長
: 每次都拿掉周長能夠減少最多的那個點
: 直到周長小於或等於繩子的長度
作者: cocoyan (摳摳厭)   2016-01-27 15:01:00
推,你是對的,我考慮得太少了

Links booklink

Contact Us: admin [ a t ] ucptt.com