[計(jì)算機(jī)]水平序的Graham-Scan算法

1、.#include <iostream>#include <algorithm>#include <cmath>using namespace std;typedef double Type; / 注意下面的fabs()const int maxn = 1005;const double EPS = 1e-8;const double Pi = acos(-1.0);typedef struct Point Type x, y; Point () Point (Type & xx, Type & yy) : x(xx), y(yy) Poin

2、t;/ 判斷正負(fù).int dblcmp(Type d) if (fabs(d) < EPS) return 0; / 注意數(shù)據(jù)類型不同，abs()也不同. return d > 0 ? 1 : -1;/ 叉乘. cross product of (c->a) and (c->b).Type Cross(Point & c, Point a, Point b) return (a.x - c.x) * (b.y - c.y) - (b.x - c.x) * (a.y - c.y);Type Distance(Point & u, Point & v

3、) return sqrt( 0.0 + (u.x - v.x) * (u.x - v.x) + (u.y - v.y) * (u.y - v.y) );int n;Point pointmaxn;int Stackmaxn;int top;double ans;bool cmp(const Point & a, const Point & b) if (a.y = b.y) return a.x < b.x; return a.y < b.y;void graham_scan() int i; int temp_top; if (n <= 1) top =

4、0; return ; sort(point, point + n, cmp); / point0即為起點(diǎn). / 做右鏈. top = -1; Stack+top = 0; Stack+top = 1; for (i = 2; i < n; i+) while (top >= 1 && dblcmp(Cross(pointStacktop - 1, pointi, pointStacktop) >= 0) top-; / 如果不能左轉(zhuǎn)，則退棧. 如果只要求極點(diǎn)，則共線的點(diǎn)也是不要的(即要加等于). Stack+top = i; temp_top = top;

5、/ 此時(shí)的棧頂元素一定是第n個(gè)點(diǎn). / 做左鏈. Stack+top = n - 2; for (i = n - 3; i >= 0; i-) while (top >= temp_top + 1 && dblcmp(Cross(pointStacktop - 1, pointi, pointStacktop) >= 0) top-; / 如果不能左轉(zhuǎn)，則退棧. 如果只要求極點(diǎn)，則共線的點(diǎn)也是不要的(即要加等于). Stack+top = i; / 此時(shí)的棧頂元素是第1個(gè)點(diǎn).(如果凸包是一條直線，則左右鏈倒置相同.) / 凸包的頂點(diǎn)為pointStack0 到

6、 pointStacktop - 1.int main(void) int i; scanf("%d", &n); for (i = 0; i < n; i+) scanf("%lf %lf", &pointi.x, &pointi.y); graham_scan(); ans = 0; for (i = 0; i < top; i+) printf("%lf %lfn", pointStacki.x, pointStacki.y); ans += Distance(pointStacki, pointStacki + 1); / pointStacktop