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