很典型的凸包问题。我一开始想繁了，因为我想如果是个凹多边形，可能最终的围墙也可能是凹的，后来想起题中的要求是最小的长度，而凹的围墙虽然离castle距离精确的等于r，可是长度并不是最小的，只有凸包的长度才是最小的。因此问题就简单很多，先求凸包，再求所有边的长度和，最后加上一个2*PI*r，这是所有凸包点处的弧的长度和。
代码我就不发了，因为我是用的模板，关键代码没自已写，顺便也测试下模板正确性。
posted on 2009-06-26 13:34
古月残辉 阅读(964)
评论(1) 编辑 收藏 引用 所属分类:
计算几何