存档

文章标签 ‘模拟退火’

POJ 2420 A Star not a Tree? 多边形费马点

2010年11月29日 没有评论

POJ 2420 A Star not a Tree?实际上就是求平面内多边形的费马点问题,只不过这里要的不是点,而是最短距离。这里使用模拟退火的方法来逼近费马点。所谓费马点就是指满足这样条件的一个点:这个点到多边形所有定点的距离和最短。
平面上三角形的费马点有如下性质:

  1. 若三角形ABC的3个内角均小于120°,那么3条距离连线正好平分费马点所在的周角。
  2. 若三角形有一内角不小于120度,则此钝角的顶点就是距离和最小的点。

这次福州赛区考了个四边形的费马点,但是我们悲剧的卡在了Wron[......]

继续阅读