$二维凸包$

$问题描述$

平面直角坐标系上有 $n$ 个点，

在平面上能包含所有给定点的周长最短的凸多边形叫做凸包。

$Andrew算法$

算法步骤如下：

1. 将所有点按横坐标为第一关键字，纵坐标为第二关键字排序
2. 从左到右扫描每个点，如果新点 $P$ ，在栈顶两元素构成直线的左面，则弹出栈顶元素
3. 将新点入队
4. 扫描完成后，栈中所有点构成上凸壳，再次从右向左扫描

时间复杂度 $O(n \log n)$

$实现$

#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef pair<double, double> PDD;
const int N = 10010;
int n, q[N];
PDD a[N];

double cross(double x1, double y1, double x2, double y2)
{
    return x1 * y2 - x2 * y1;
}

double area(PDD a, PDD b, PDD c)
{
    return cross(b.x - a.x, b.y - a.y, c.x - a.x, c.y - a.y);
}

double Andrew()
{
    double res = 0;
    int hh = 0, tt = -1;
    for (int i = 0; i < n; i ++ )
    {
        while (hh < tt && area(a[q[tt - 1]], a[q[tt]], a[i]) >= 0) tt -- ;
        q[++ tt] = i;
    }
    for (int i = 1; i <= tt; i ++ )
    {
        double dx = a[q[i]].x - a[q[i - 1]].x, dy = a[q[i]].y - a[q[i - 1]].y;
        res += sqrt(dx * dx + dy * dy);
    }
    hh = 0, tt = -1;
    for (int i = n - 1; i >= 0; i -- )
    {
        while (hh < tt && area(a[q[tt - 1]], a[q[tt]], a[i]) >= 0) tt -- ;
        q[++ tt] = i;
    }
    for (int i = 1; i <= tt; i ++ )
    {
        double dx = a[q[i]].x - a[q[i - 1]].x, dy = a[q[i]].y - a[q[i - 1]].y;
        res += sqrt(dx * dx + dy * dy);
    }
    return res;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%lf%lf", &a[i].x, &a[i].y);
    sort(a, a + n);
    printf("%.2lf", Andrew());
    return 0;
}