反例: 四个点分别为 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://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1512891798.A.ACE.html ※ 编辑: iago2007 (118.160.84.116), 01/03/2018 13:57:45