pku1266 atan2的应用

1个评论20次阅读2008.09.02 20:52; 作者：Felicia　

amath
我的做法是

  • 求外接圆圆心
  • 求出包围这个圆的最小矩形
  • 求出圆的最上，最下，最左，最右点
  • 求出这四个点中在圆上的点，这样我们得到点集`p`
  • 若这些点在矩形内部，则不断缩小矩形，直到不能缩小为止，输出答案

关键是判断点是否在圆弧上。我的方法是：设`A, B`为圆弧端点，`C`为圆弧上一点，`P`是待判断点，计算`B,C,P`相对`A`的极角`b,c,p`，若`(b – c) * (b – p) >= 0`则`p`在圆弧上。另外比较实数的时候一定要用eps，否则会WA。

endamath

相关文章

标签云: | 日志分类: 计算几何
如需转载烦请添加以下信息: 本文转自Felicia@GCCFeli.cn

  • 评论 (1)
  • 引用通告 (0)
发表评论 引用通告

  • zhuimeng | 回复 1F

    四月 21st, 2011 at 22:55

    膜拜大神、、、计算几何新人

暂无引用通告