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