※ 引述《obelisk0114 (追风筝的孩子)》之铭言： : 之前看到一题十分困难的题目,大致长这样: : 平面上有许多点,要用一条固定长度的绳子圈住最多点 : 绳子需要头尾相连 : 由於题目并未提到其他限制,所以任意形状的圈法都可以 : 目前只有想到用凸多边形去围 : 但是实际做法没有头绪 : 各位大大有何想法 ? 先把所有点用一个凸多边形包住 凸多边形的每一个角都至少代表一个点 由於三角形的两边长必大於第三边 所以拿掉其中一个角後 再用新的凸多边形把剩下来的点包住 新凸多边形的周长会小於或等於原本的周长 每次都拿掉周长能够减少最多的那个点 直到周长小於或等於绳子的长度 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 114.24.19.70 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1512814263.A.C02.html