叉积
有两个平面向量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) $
标签：LITTLE,int,double,几何,凸包,算法,&&,poi,include From： https://www.cnblogs.com/PeppaEvenPig/p/18428267