叉积
有两个平面向量a, b，那么有 a $ \times $ b $ = x_a \times y_b - x_b \times y_a $；
这是有方向的，且遵守右手定则，正代表 a 逆时针转到 b，负代表顺时针；
凸包
求凸包，我用的 $ Graham $ 扫描法；
首先把最底下的点找出来，然后按照其它点对于这个点的角度排序，然后用一个类似于单调栈的东西维护一下即可；
时间复杂度： $ \Theta(n \log n) $
例题：Luogu P2742
点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
int n;
struct poi{double x, y;double operator ^(const poi &A) const {return x * A.y - y * A.x;}
}e[500005], s[500005];
int cnt;
double dis(poi x) {return sqrt(x.x * x.x + x.y * x.y);
}
bool cmp(poi x, poi y) {poi a = {x.x - e[1].x, x.y - e[1].y};poi b = {y.x - e[1].x, y.y - e[1].y};double c = a ^ b;if (c > 0.0) return 1;else if (c == 0.0 && dis(a) <= dis(b)) return 1;else return 0;
}
int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n;for (int i = 1; i <= n; i++) {cin >> e[i].x >> e[i].y;if (i != 1 && (e[1].y > e[i].y || (e[1].y == e[i].y && e[1].x > e[i].x))) swap(e[1], e[i]);}sort(e + 2, e + 1 + n, cmp);s[1] = e[1];cnt = 1;for (int i = 2; i <= n; i++) {poi a = {s[cnt].x - s[cnt - 1].x, s[cnt].y - s[cnt - 1].y};poi b = {e[i].x - s[cnt].x, e[i].y - s[cnt].y};while(cnt > 1 && ((a ^ b) <= 0.0)) {cnt--;a = {s[cnt].x - s[cnt - 1].x, s[cnt].y - s[cnt - 1].y};b = {e[i].x - s[cnt].x, e[i].y - s[cnt].y};}s[++cnt] = e[i];}s[++cnt] = e[1];double ans = 0.0;for (int i = 2; i <= cnt; i++) {ans += dis({s[i].x - s[i - 1].x, s[i].y - s[i - 1].y});}cout << fixed << setprecision(2) << ans;return 0;
}
旋转卡壳
以求凸包直径为例，我们的这个算法就是拿一组平行线去卡凸包，最后看哪个最大即可；
用双指针维护一下，每次找凸包的一条边，然后找最远的点即可；
时间复杂度：$ \Theta(n) $
