凸包问题

给定义一些点，求能把所有这些点包含在内的面积最小的多边形，可以想象有一个很大橡皮箍，它把所有的点都箍在里面，在橡皮箍收紧之后，绕着最外围的点形成的多边形就是凸包。如下图：

Graham扫描法

时间复杂度：O(n㏒n)
思路：Graham扫描的思想和Jarris步进法类似，也是先找到凸包上的一个点，然后从那个点开始按逆时针方向逐个找凸包上的点，但它不是利用夹角。

步骤：

1. 把所有点放在二维坐标系中，则纵坐标最小的点一定是凸包上的点，如图中的P0。
2. 把所有点的坐标平移一下，使 P0 作为原点，如上图。
3. 计算各个点相对于 P0 的幅角 α ，按从小到大的顺序对各个点排序。当 α 相同时，距离 P0 比较近的排在前面。例如上图得到的结果为 P1，P2，P3，P4，P5，P6，P7，P8。我们由几何知识可以知道，结果中第一个点 P1 和最后一个点 P8 一定是凸包上的点。
   （以上是准备步骤，以下开始求凸包）
   以上，我们已经知道了凸包上的第一个点 P0 和第二个点 P1，我们把它们放在栈里面。现在从步骤3求得的那个结果里，把 P1 后面的那个点拿出来做当前点，即 P2 。接下来开始找第三个点：
4. 连接栈顶和次栈顶的两个点，得到直线 L 。看当前点是在直线 L 的右边还是左边。如果在直线的右边就执行步骤5；如果在直线上，或者在直线的左边就执行步骤6。
5. 如果在右边，则栈顶的那个元素不是凸包上的点，把栈顶元素出栈。执行步骤4。
6. 当前点是凸包上的点，把它压入栈，执行步骤7。
7. 检查当前的点是不是步骤3那个结果的最后一个元素 P8 。如果是就结束。如果不是的话就把原当前点后面那个点做新的当前点，返回步骤4。
   最后，栈中的元素就是凸包上的点了。

以下为用Graham扫描法动态求解的过程：

// 模板题 hdu-1392（http://acm.hdu.edu.cn/showproblem.php?pid=1392）
#include<bits/stdc++.h>

using namespace std;

const double eps = 1e-8;

struct point { // 点
    double x, y;
    double dis(point n1) {
        return sqrt((x-n1.x)*(x-n1.x) + (y-n1.y)*(y-n1.y));
    }
}p0;

bool op1(const point a, const point b) { // 初始排序
    return (a.y == b.y) ? a.x<b.x : a.y<b.y;
}
bool op2(const point a, const point b) { // 极角排序
    double A = atan2(a.y-p0.y,a.x-p0.x);
    double B = atan2(b.y-p0.y,b.x-p0.x);
    return (A == B) ? a.x<b.x : A < B;
}

double cross(point a, point b, point c, point d) { // 叉积
    return (b.x-a.x)*(d.y-c.y) - (b.y-a.y)*(d.x-c.x);
}

int main() {
    int n; while(~scanf("%d", &n),n) {
        vector<point> p(n);
        for(int i = 0; i < n; ++ i) {
            scanf("%lf%lf", &p[i].x, &p[i].y);
        } if (n == 1) {printf("0.00\n"); continue;}

        sort(p.begin(), p.end(), op1); // 初始排序
        p0 = p[0]; // 确定原点
        sort(p.begin()+1, p.end(), op2); // 极角排序

        vector<point> Stack(n); int tot = 0; // 模拟栈
        Stack[tot++] = p[0]; Stack[tot++] = p[1];
        for(int i = 2; i < n; ++ i) { // 遍历当前点
            while(cross(p[i],Stack[tot-2],p[i],Stack[tot-1]) <= eps) tot --;
            Stack[tot++] = p[i];
        }

        double res = 0;
        for(int i = 0; i < tot; ++ i) {
            res += Stack[i].dis(Stack[(i+1)%tot]);
        }
        if (tot == 2) res /= 2;
        printf("%0.2f\n", res);
    }
    return 0;
}

Andrew算法

时间复杂度：O(nlogn)
Andrew算法是Craham算法的变种，它更快，更稳定。算法做两次扫描，先从最左边的点沿“下凸包”扫描到最右边，再从最右边的点沿“上凸包”扫描到最左边，“上凸包”和“下凸包”合起来就是完整的凸包。
步骤：

1. 把所有的点按照横坐标x从小到大排序，如果x相同，按y从小到大排序，并删除重复的点，得到序列 P0, P1, P2, P3, P4, P5, ..., Pm。
2. 从左边到右边扫描所有点，求“下凸包”。P0 一定在凸包上，它是凸包最左边的顶点，从P0开始，依次检查P1, P2, ..., Pm, 扩展“下凸包”。 判断的依据是：如果当前点在凸包的前行的左边，说明在“下凸包”上，把它加入到凸包；如果在右边，说明凸包方向错了，弹出凸包的栈顶元素。继续这个过程，直到检查完所有的点。
3. 从右到左重新扫描所有点，求“上凸包”。和求“下凸包”的过程类似，最右边的点 Pm 一定在凸包上。

// hud-139（http://acm.hdu.edu.cn/showproblem.php?pid=1392）
#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e4;
const double eps = 1e-8;
int sgn(double x) { // 判断x是否为零
    if (fabs(x) < eps) return 0;
    return (x<0) ? -1 : 1;
}

struct point {
    double x, y;
    point(){}
    point(double x, double y): x(x), y(y) {}
    point operator+ (point n1) {return point(x+n1.x, y+n1.y);}
    point operator- (point n1) {return point(x-n1.x, y-n1.y);}
    bool operator== (point n1) {return sgn(x-n1.x) == 0 && sgn(y-n1.y) == 0;}
    bool operator< (point n1) {return (sgn(x-n1.x)==0) ? sgn(y-n1.y)<0 : sgn(x-n1.x)<0;}
};
typedef point Vector;
double cross(Vector a, Vector b) {return a.x*b.y - a.y*b.x;} // 叉积
double dist(point a, point b) {return sqrt((b.x-a.x)*(b.x-a.x) + (b.y-a.y)*(b.y-a.y));}

int Andrew(point *p, int n, point *sta) { // Andrew算法
    int tot = 0;
    sort(p,p+n); // 排序：按x从大到小排序，如果x相同，按y排序
    n = unique(p, p+n) - p; // 去除重复点
    for(int i = 0; i < n; ++ i) { // 下凸包的顶点
        while(tot > 1 && sgn(cross(sta[tot-1]-sta[tot-2],p[i]-sta[tot-2])) <= 0) tot--;
        sta[tot++] = p[i];
    }
    int j = tot;
    for(int i = n-2; i >= 0; -- i) { // 上凸包的顶点
        while(tot > j && sgn(cross(sta[tot-1]-sta[tot-2],p[i]-sta[tot-2])) <= 0) tot --;
        sta[tot++] = p[i];
    }
    return (n > 1) ? tot -1 : tot; // 凸包的顶点数
}

int main() {
    point p[maxn], sta[maxn];
    int n; while(~scanf("%d", &n),n) {
        for(int i = 0; i < n; ++ i) {
            scanf("%lf%lf", &p[i].x, &p[i].y);
        }
        int tot = Andrew(p, n, sta); double res = 0;
        if (tot == 1) printf("0.00\n");
        else if (tot == 2) printf("%0.2f\n", dist(sta[0],sta[1]));
        else {
            for(int i = 0; i < tot; ++ i) {
                res += dist(sta[i],sta[(i+1)%tot]);
            }
            printf("%0.2f\n", res);
        }
    }
    return 0;
}

模板题：

hud-139（http://acm.hdu.edu.cn/showproblem.php?pid=1392）
参考资料：
http://blog.csdn.net/bone_ace/article/details/46239187
《算法竞赛入门到进阶》——罗勇军、郭卫斌著。