POJ1113 Wall 凸包 Andrew算法

算法讲解:

我们把所有点按照x排序,若x相容则按照y排序。然后我们准备一个栈,每次如果栈内元素>=2我们就看待加入元素与栈顶元素的连线和栈顶元素和栈第二个元素的连线的位置关系。如果在左面,就加入。否则,就删除最近加入的点。直到在左面。然后我们这样子就求出了下凸包。然后我们只要再反着求一遍上凸包即可。

题目讲解:

图片来自http://blog.csdn.net/r1986799047/article/details/48243105

然后我们只需要求出城堡的凸包再加上一个半径构成的圆的周长即可。详情可参考上图,一目了然。poj输出浮点数记得使用%f,%lf会莫名奇妙的WA。

当时调了好久,一直有非常鬼畜的问题。赋值发生奇怪的事情。后来发现定义类型的构造函数写残了。debug了1个多小时…….

AC代码:

发表评论