随笔-20  评论-16  文章-36  trackbacks-0

      很典型的凸包问题。我一开始想繁了,因为我想如果是个凹多边形,可能最终的围墙也可能是凹的,后来想起题中的要求是最小的长度,而凹的围墙虽然离castle距离精确的等于r,可是长度并不是最小的,只有凸包的长度才是最小的。因此问题就简单很多,先求凸包,再求所有边的长度和,最后加上一个2*PI*r,这是所有凸包点处的弧的长度和。
      代码我就不发了,因为我是用的模板,关键代码没自已写,顺便也测试下模板正确性。

posted on 2009-06-26 13:34 古月残辉 阅读(977) 评论(1)  编辑 收藏 引用 所属分类: 计算几何

评论:
# re: POJ 1113 Wall 2009-08-26 16:42 | Figther
你用的什么模版啊,模版发一下好吧~~  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理