凸包

点的有序化

凸包算法多要先对点进行排序。点排序的主要方法有两种——极角排序和水平排序。

极角排序

极角排序一般选择一个点做极点，然后以这个点为中心建立极坐标，将输入的点按照极角从小到大排序，如果两个点的极角相同，那么将距离极点较远的点排在前面。

但在实践过程中，一般不进行真正的极角排序，而是通过进行叉积比较，并不真的计算出点的极角。这种做法可以避免使用对精度影响较大的三角函数运算，对精度影响较小。

水平排序

水平排序将所有点按照$y$坐标从小到大排列，$y$坐标相同的则按照$x$坐标从小到大排序。选取排序后最前面的$A$点和最后面的$B$点，将$\vec{AB}$右边的点按照次序取出，再将左侧的点按照次序逆序取出后连起来就是最终的结果。

凸包求法

Graham 扫描法

Graham算法是求解静态凸包较好的一种算法，时间复杂度为$n\log n$，尤其在求解大量点构成的凸包时，能消耗较少的时间。

算法简述

Graham算法首先要求将无序的点有序化（参见前面的点的有序化）。Graham算法会维持一个栈，栈中的点为输出凸包上的点。Graham算法首先选择一个肯定在凸包上的点入栈，并按照点的顺序将点依次入栈。如果栈中元素数大于1，那么每次入栈前，检查栈顶两个点和新入栈的点是否能保持凸性（设栈顶元素为$P_0P_1$，新入栈点为$Q$，那么它们要满足$\vec{P_{top-1}P_{top}} \times \vec{P_{top}Q} \geq 0$才能维持凸性）。如果不能满足，则不断出栈知道能满足凸性或元素数不大于1位置，并将新点入栈。重复上述过程，就能得到凸包。

Graham算法本身的时间复杂度为$O(n)$，所以算法时间复杂度取决与点的点的有序化的时间复杂度，通常为$O(n\log n)$，如果输入的点已经为有序化的点，那么无序排序，直接进行Graham算法，总时间复杂度为$O(n)$。

实现细节的注意事项

极角大小问题

实际实现Graham算法的极角排序并不是真正的按照极角大小排序，因为计算机在表示和计算浮点数时会有一定的误差。一般会利用叉积判断两个点的相对位置来实现极角排序的功能。假设以确定平面中最下最左的点（基准点）$P$，并已知平面上其它两个不同的点$AB$。若点$A$在向量$PB$的逆时针方向，那么我们认为$A$的极角大于$B$的极角，反之$A$的极角小于$B$的极角（具体实现应借助叉积）。

极角相同点的处理

在Graham算法中，经常会出现两个点极角相同的情况。对于具有相同极角的两个不同点$AB$，那么我们应该把$AB$两点的按照距离基准点距离的降序排列。而对于完全重合的两点，可以暂不做处理。

模板代码

typedef vector<Pt> Convex;

// 排序比较函数，水平序
bool comp_less(Pt a, Pt b) {
    return sgn(a.x-b.x) < 0 || (sgn(a.x-b.x) == 0 && sgn(a.y-b.y) < 0);
}

// 返回a中点计算出的凸包，结果存在res中
void convex_hull(Convex &res, vector<Pt> a) {
    res.resize(2 * a.size() + 5);
    sort(a.begin(), a.end(), comp_less);
    a.erase(unique(a.begin(), a.end()), a.end());
    int m = 0;
    for (int i = 0; i < int(a.size()); ++i) {
        while (m>1 && sgn(det(res[m-1] - res[m-2], a[i] - res[m-2])) <= 0)
            --m;
        res[m++] = a[i];
    }
    int k = m;
    for (int i = int(a.size()) - 2; i >= 0; --i) {
        while (m>k && sgn(det(res[m-1] - res[m-2], a[i] - res[m-2])) <= 0)
            --m;
        res[m++] = a[i];
    }
    res.resize(m);
    if (a.size() > 1) res.resize(m-1);
}

经典题目

• POJ 1113 Wall
• POJ 3348 Cows

旋转卡壳

简介

旋转卡壳一般用于求凸包上最远的点的距离，这个距离也称为凸包的直径。旋转卡壳可以在$O(n)$的时间复杂度内找出最远的点对。

算法简述

如下图，假设$A$与$B$是凸包上最远的点对，那么过$A$和$B$分别做两条平行的直线并进行旋转，使过$A$的直线与$A$的相邻点$P$重合（图中红线）。那么点$B$一定凸包上距离直线$AP$最远的点，这样的话，$\triangle_{ABP}$一定以$AP$为底边以另一个凸包上的顶点形成的三角形中面积最大的。如果我们枚举凸包上所有的相邻点组成的边并找出距离这条边最远的点，最远点对一定在这个三角形中。因为在我们按照逆时针枚举所有边的同时，距离它们最远的点的变化方向也是逆时针的，所以整个算法的时间复杂度是$O(n)$的。

模板代码

// 计算凸包a的直径
double convex_diameter(const Convex &a, int &first, int &second) {
    int n = a.size();
    double ans = 0.0;
    first = second = 0;
    if (n == 1) return ans;
    for (int i = 0, j = 1; i < n; ++i) {
        while (sgn(det(a[nxt(i)]-a[i], a[j]-a[i]) - det(a[nxt(i)]-a[i], a[nxt(j)]-a[i])) < 0)
            j = nxt(j);
        double d = max((a[i]-a[j]).norm(), (a[nxt(i)]-a[nxt(j)]).norm());
        if (d > ans) ans=d, first=i, second=j;
    }
    return ans;
}

经典题目

• POJ 2187 Beauty Contest
• POJ 2079 Triangle
• POJ 2007 Scrambled Polygon