基本概念和存储方式

• 点：坐标
• 线段：两个端点
• 直线/射线：两个点/点+斜率
• 多边形：逆时针/顺时针顺序存储顶点
• 圆：圆心+半径
• 向量：与点相同

点积

$ \begin{aligned} a \cdot b &= |a||b|\cos \theta \\\ &= a.x * b.x + a.y * b.y \end{aligned} $

• 物理意义是做功
• $a$ 与 $b$ 垂直时点积为 $0$

叉积

$ \begin{aligned} a \times b &= |a| |b| \sin \theta \\\ &= a.x * b.y - a.y * b.x \end{aligned} $

• 几何意义是四边形不等式面积。
• $a$ 与 $b$ 共线时叉积为 $0$；$b$ 在 $a$ 逆时针方向时叉积为正；$b$ 在 $a$ 顺时针方向时叉积为负。

多边形面积

• 将顶点按逆时针顺序排序
• 相邻顶点叉乘后求和，最后乘上 $\frac{1}{2}$ 就是多边形面积

凸包

二维凸包：平面上有一些点，现要找一个最小的凸多边形，使得能够覆盖所有的点，这个凸多边形即为二维凸包。

高维凸包同理。

Graham 扫描法

$\rm{Graham}$ 扫描法维护一个 凸壳
通过不断在凸壳中加入新的点和去除影响凸性的点，最后形成凸包
主要分为排序和扫描两个步骤

(1) 排序

先找到一个 $y$ 值最小（有相同的则选取 $x$ 值最小）的点，作为构造凸壳的起点
将剩下的点按照极角（与起点连线后同 $x$ 轴的夹角）升序（逆时针）排序。

(2) 扫描

起点入栈，按刚才的顺序扫描每一个点。如果当前点与栈顶两点构成了凹多边形，则栈顶的点一定不在构成凸包点集上，出栈，继续对新的栈顶两点做如上判断，否则当前点入栈。

相当于在扫描的过程中维护其凸性。如此最终一定能构成凸包。

例1. 【模板】二维凸包

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)

using std::cin;
using std::cout;

const int MX = 100005;

int n, top;

struct Point {
    double x, y;
    Point(double x=0, double y=0): x(x), y(y) {}
} p[MX], st[MX];

double cross(Point &a1, Point &a2, Point &b1, Point &b2) { // 检查叉乘是否大于0，如果是，则 a 逆时针转到 b
    return (a2.x-a1.x)*(b2.y-b1.y) - (b2.x-b1.x)*(a2.y-a1.y);
}
double dist(Point p1, Point p2) {
    return sqrt((p2.x-p1.x)*(p2.x-p1.x) + (p2.y-p1.y)*(p2.y-p1.y));
}

bool cmp(Point p1, Point p2) {
    double res = cross(p[1], p1, p[1], p2);
    if (res > 0) return true;
    if (res == 0 and dist(p[0], p1) < dist(p[0], p2)) return true;
    return false;
}

int main() {
    cin >> n;

    rep(i, n) cin >> p[i].x >> p[i].y;

    for (int i = 2; i <= n; ++i) {
        if (p[i].y < p[1].y or (p[i].y == p[1].y and p[i].x < p[1].x)) {// 找到起点
            std::swap(p[1], p[i]);
        }
    }

    std::sort(p+2, p+n+1, cmp); // 按照极角排序

    st[top=1] = p[1]; // 起点入栈
    for (int i = 2; i <= n; ++i) { // 扫描的过程中遇到不满足凸性的点则弹栈
        while (top > 1 and cross(st[top-1], st[top], st[top], p[i]) <= 0) {
            top--;
        }
        st[++top] = p[i]; // 当前点入栈
    }
    st[top+1] = p[1]; // 起点也是终点，这样是完整凸包

    double ans = 0;
    rep(i, top) {
        ans += dist(st[i], st[i+1]);
    }

    printf("%.2lf\n", ans);

    return 0;
}