本笔记正在更新！ 欢迎催更！
(sf Part -999) 感谢列表
（排名不分先后）
- 计算几何「OI-Wiki」
- 数论小白都能看懂的平面凸包详解 「ShineEternal的博客」
- 几何画图「GeoGebra」 离线版
- 感谢@rui_er 指出了一个错误
(sf Part 1) 前言
听说 rui_er 神仙做梦学了二维凸包后，我也想学学了计算几何，可是咱没人家的天赋，可以通过睡觉学，只能看资料学了/dk
@rui_er 快写篇文章教教我们怎么做梦学/se（
回归正题，首先说明一下，本人是刚学 (mathsf{OI}) 的萌新，本学习笔记如有错误，并非有意，但仍然欢迎在讨论去狂 (sf D) 她。
另：本文各个部分的讲解顺序 并不按照难度排序，而是按照我学习的顺序，请选择合适的内容观看。
关于图片：本文所有图片均为作者纯手画 是 rui_er 做梦时托梦给我的（
(sf Part 2) 何为计算几何
计算几何，就是利用计算机建立数学模型解决几何问题。
要用电脑解几何题？数学好的同学们笑了。
要用电脑解几何题？rui_er 笑了，我做梦就解决了（不是
我们并不是用计算机算数学卷子上的几何题去了，而是解决一些更加复杂的几何相关问题。
为了解决复杂且抽象的问题，我们一定要选择合适的研究方法。对于计算机来说，给它看几何图形……
(sf Part 3) 凸包
(sf Part 3.1) 二维凸包
(sf Part 3.1.1) 凸多边形
凸多边形是指所有内角大小都在 ([0, pi]) 范围内的 简单多边形 。
(sf Part 3.1.2) 凸包
「
在平面上能包含所有给定点的最小凸多边形叫做凸包。
其定义为：对于给定集合 (X) ，所有包含 (X) 的凸集的交集 (S) 被称为 (X) 的 凸包 。
(qquadqquad) —— OI-Wiki
」
其实我们可以把凸包看成一个拿橡皮筋围成的一个图形。
假设有一个布满小凸起的板子：
我们要把这些凸起都围起来，怎么围呢？
显然，最简单方变的方法是这样：
但是，我们知道，橡皮筋是有弹力的，所以橡皮筋会往里缩，直到这样：
最外圈的凸起撑起了橡皮筋。
此时橡皮筋围成的多边形的顶点就是最外圈凸起所在的位置。
由此，我们就定义橡皮筋围成的图形为一个平面凸包。
那么，换一种定义，就为：
平面凸包是指覆盖平面上 (n) 个点的最小的凸多边形。
当然，我们发现在程序中却无法模拟橡皮筋收缩的过程，于是有了下文的诞生。
(sf Part 3.1.3) 二维凸包的求法
(sf Part 3.1.3.1) 斜率逼近法
其实这也是一种容易想到的算法，但是并不常用（代码复杂度高），所以我们省略带过。
(sf Part 3.1.3.2) Jarvis 算法
这其实是一种数学构造法
此算法的时间复杂度为 (O(nm))。
但是，这个复杂度会爆炸。
于是我们伟大的 (sf OIer) 就想到了 Graham 算法。
(sf Part 3.1.3.3) Graham 算法
Graham 算法的本质：
Graham 扫描算法维护一个凸壳，通过不断在凸壳中加入新的点和去除影响凸性的点，最后形成凸包。
凸壳：凸包的一部分。
此算法主要分为两部分：
- 排序
- 扫描
(sf Part 3.1.3.3.1) 排序
我们先选择一个 (y) 最小的点（如 (y) 相同选 (x) 最小），记为 (p_1)。
剩下的点，按照极角的大小逆时针排序，记为 (p_2,p_3,dots, p_m)。
我们按照排序结束时的顺序枚举每一个点，依次连线，这里可以使用一个栈来存储，每次入栈，如果即将入栈的元素与栈顶两个元素所构成了一个类似于凹壳的东西，那么显然处于顶点的那个点一定不在这个点集的凸包上，而他正好在栈顶，所以把它弹出栈，新点入栈。——节选自 数论小白都能看懂的平面凸包详解 - ShineEternal的博客
(sf Part 3.1.3.3.2) 扫描
（下列所说的左右等是指以上一条连线为铅垂线，新的连线偏移的方向）
刚开始，我们的点集是这样的：
(p_1) 为起始点。
随后，(p_2) 准备入栈，由于栈元素很少，所以可以入栈。
再看 (p_3)，因为 (p_3) 向左，符合凸包条件，入栈。
随后 (p_4) 也一切正常，依然向左，入栈。
(p_5) 依然向左，入栈。
到 (p_6) 时，我们发现了点问题，就是不再是向左了，而是向右了，所以我们此时要将 (p_5) 出栈，(p_6) 入栈。
入栈后，我们发现，相对于 (p_4)，(p_6) 依然是向右的，所以我们还要把 (p_4) 出栈，(p_6) 入栈。
接下来 (p_7) 没有问题。
(p_8) 时，我们发现，也是向右的，所以将 (p_7) 出栈，(p_8) 入栈。
接下来 (p_9) 正常，入栈。
最后，我们再把最后一个点和第一个点连起来。
此时，我们的 Graham 算法的全过程就结束了。
扫描的时间复杂度：(O(n))。
但是不可能那么优秀，还要加上排序的时间复杂度：(O(nlog n))。
所以总时间复杂度为 (O(n log n))。
可见此算法相比之前的算法优秀的多。
(sf Part 3.1.3.4) Andrew 算法
假设我们有这些点：
首先把所有点以横坐标为第一关键字，纵坐标为第二关键字排序。
相对于 Graham 算法来说，Andrew 算法排序更简单，按 (x, y) 坐标排序，时间复杂度也更低（一般的坐标系中排序方法）。
首先将 (p_1) 入栈。
然后也将 (p_2) 入栈，(p_2) 可能在，也可能不在，等着之后判断。
随后，发现 (p_3) 偏右，所以我们将 (p_2) 出栈。
发现 (p_4) 依然偏右，(p_3) 出栈，(p_4) 入栈。
(p_5) 向右，(p_4) 出栈，(p_5) 入栈。
(p_6) 向左，入栈。
(p_7) 向右，(p_6) 出栈，(p_7) 入栈。
(p_8) 向右，(p_7) 出栈，继续检查发现相对于 (p_5) (p_8) 仍然向右，(p_5) 出栈，(p_8) 入栈。
此时，我们发现，凸包明明还空一半就到头了？？？
然而这是意料之中，我们这种算法必然会只算出一半的凸包。
所以我们需要再从排序末尾的点（也就是 (p_8)）出发，按照一模一样的方式再算一遍就行了。
当然如果我们走过的点就不许要再走了（除了 (p_1)）
从 (p_8) 到 (p_7)，向左，(p_7) 入栈。
(p_6) 向右，(p_7) 出栈，(p_6) 入栈。
(p_5) 向左，入栈。
(p_4) 向左，入栈。
(p_3) 向右，(p_4) 出栈，对于 (p_5) (p_3) 依然向右，(p_5) 出栈，(p_3) 入栈。
(p_2) 向右，(p_3) 出栈，(p_2) 入栈。
最后将 (p_2) 和 (p_1) 连起来。
至此，我们的 Andrew 算法就完成了！
扫描的时间复杂度：(O(n))（已过滤常数）
排序时间复杂度：(O(n log n))
总时间复杂度：(O(n log n))
(sf Part 3.1.4) 实战演练
(sf Part 3.1.4.1) P2742 [USACO5.1]圈奶牛Fencing the Cows /【模板】二维凸包
先拿模板题练练手。
题目简述：求一个点集凸包的边长和。
拿 Graham 算法做即可。
直接套模板即可，手写栈应该更快（？
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#define line cout << endl
using namespace std;
const int NR = 1e5 + 5;
int n;
double ans;
struct point {
double x, y;
};
point p[NR], ps[NR];
double dis (point pa, point pb) { //求两点间距离
return sqrt ((pb.x - pa.x) * (pb.x - pa.x) + (pb.y - pa.y) * (pb.y - pa.y));
}
double cp (point pa1, point pa2, point pb1, point pb2) { //求叉积
return (pa2.x - pa1.x) * (pb2.y - pb1.y) - (pb2.x - pb1.x) * (pa2.y - pa1.y);
}
bool cmp (point px, point py) { //排序
double num = cp (p[1], px, p[1], py);
if (num > 0) return true;
if (num == 0 && dis (p[0], px) < dis (p[0], py)) return true;
return false;
}
int main () {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> p[i].x >> p[i].y;
if(i != 1 && p[i].y < p[1].y) { //去重
swap (p[i].y, p[1].y);
swap (p[i].x, p[1].x);
}
}
sort (p + 2, p + n + 1, cmp);
ps[1] = p[1]; //最低点是肯定在凸包里的
int h = 1;
for (int i = 2; i <= n; i++) {
while (h > 1 && cp (ps[h - 1], ps[h], ps[h], p[i]) <= 0) { //判断是向左还是向右，如果向右就出栈
h--;
}
h++;
ps[h] = p[i];
}
ps[h + 1] = p[1]; //最后一个点跟第一个点相连
for (int i = 1; i <= h; i++) {
ans += dis (ps[i], ps[i + 1]); //累加
}
printf ("%.2lf
", ans);
return 0;
}
(sf Part 3.1.4.2) UVA11626 Convex Hull
拿 Andrew 练练手吧qaq，也是道模板题，但是好像拿 Graham 会 TLE（？
/*
Problem:UVA11626
Dpte:03/07/20 14:05
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#define line cout << endl
using namespace std;
const int NR = 1e5 + 5;
const double eps = 1e-7;
int n;
struct point {
double x, y;
point () {}
point (double a, double b) : x (a), y (b) {}
bool operator < (const point &b) const {
if (x < b.x) return 1;
if (x > b.x) return 0;
return y < b.y;
}
point operator - (const point &b) {
return point (x - b.x, y - b.y);
}
};
point p[NR], sp[NR];
int cmp (double x) {
if (fabs (x) < eps) return 0;
return x > 0 ? 1 : -1;
}
double dis (point a, point b) {
return sqrt ((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
double cp (point a, point b) {
return a.x * b.y - a.y * b.x;
}
int Andrew () {
sort (p + 1, p + 1 + n);
int len = 0;
for (int i = 1; i <= n; i++) {
while (len > 1 && cmp (cp (sp[len] - sp[len - 1], p[i] - sp[len - 1])) < 0)
len--;
sp[++len] = p[i];
}
int k = len;
for (int i = n - 1; i >= 1; i--) {
while (len > k && cmp (cp (sp[len] - sp[len - 1], p[i] - sp[len - 1])) < 0)
len--;
sp[++len] = p[i];
}
return len;
}
int main () {
int t;
cin >> t;
while (t--) {
cin >> n;
char c;
for (int i = 1; i <= n; i++)
cin >> p[i].x >> p[i].y >> c;
int t = Andrew();
cout << t - 1 << endl;
for (int i = 1; i < t; i++)
printf ("%.0lf %.0lf
", sp[i].x, sp[i].y);
}
return 0;
}