作者obelisk0114 (追风筝的孩子)
看板Prob_Solve
标题[问题] 绳子围石头
时间Sat Nov 18 19:36:06 2017
之前看到一题十分困难的题目,大致长这样:
平面上有许多点,要用一条固定长度的绳子圈住最多点
绳子需要头尾相连
由於题目并未提到其他限制,所以任意形状的圈法都可以
目前只有想到用凸多边形去围
但是实际做法没有头绪
各位大大有何想法 ?
--
肝不好 ▁▁ ● ◤
肝若好
人生是黑白的 ▏ ◤
考卷是空白的
▏ ◤
、 ﹐
● ●b 囧 ▎ ●> ● ◤
▌ ﹍﹍ ０ ▊囧＞
干...
▲ ■┘ ■ ▎ ■ █◤ ▌ ㄏ▋ ︶■
〈﹀ ∥ ▁▁∥ ▎ ﹀〉◤
▋ ▊ 〈\
ψcockroach727
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 47.149.227.123
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1511004973.A.C35.html
1F：推 DJWS: 换句话说就是找「刚好包含k个点、周长最短的凸多边形」 11/18 21:06
3F：→ DJWS: 用上面网页的做法 然後穷举试误or二分搜寻k是多少 11/18 21:07