「v4」0x70 计算几何
同步于 2026-11-11,花费 14,451,581 tok。
0x71 计算几何 I
计算几何基础
0x71 计算几何全家桶(i64).cpp:
// 二维点
struct point {
i64 x, y;
point() {}
point(i64 x, i64 y) : x(x), y(y) {}
};
point operator + (point a, point b) {
return point(a.x + b.x, a.y + b.y);
}
point operator - (point a, point b) {
return point(a.x - b.x, a.y - b.y);
}
point operator * (point a, i64 b) {
return point(a.x * b, a.y * b);
}
// 叉积
i128 cross(point a, point b) {
return i128(a.x) * b.y - i128(a.y) * b.x;
}
// ab 与 ac 的叉积
// 检测连续三个点的凸性,按 x 递增时 >0 下凸 <0 上凸,按 x 递减时反之
i128 cross(point a, point b, point c) {
return i128(b.x - a.x) * (c.y - a.y) - i128(c.x - a.x) * (b.y - a.y);
}0x72 计算几何 II
凸壳
0x72 凸壳.cpp:
// 凸壳(默认:按 x 递增的上凸壳)
auto gethull(std::vector<point> s) {
std::sort(s.begin(), s.end(), [] (point l, point r) -> bool {
return l.x != r.x ? l.x < r.x : l.y > r.y; // 若要求下凸壳,改成 l.y < r.y
});
std::vector<point> h;
for (point p : s) {
if (h.size() && h.back().x == p.x) {
continue;
}
while (h.size() >= 2 && cross(h.rbegin()[1], h.back(), p) >= 0) { // 若要求下凸壳,改成 <=
h.pop_back();
}
h.push_back(p);
}
return h;
}凸包
0x72 凸包.cpp:
// 凸包(默认:逆时针)
auto gethull(std::vector<point> s) {
std::sort(s.begin(), s.end(), [] (point l, point r) -> bool {
return l.x != r.x ? l.x < r.x : l.y < r.y;
});
s.erase(std::unique(s.begin(), s.end(), [] (point l, point r) -> bool {
return l.x == r.x && l.y == r.y;
}), s.end());
std::vector<point> h;
for (int i = 0; i < s.size(); i ++) {
while (h.size() >= 2 && cross(h.rbegin()[1], h.back(), s[i]) <= 0) {
h.pop_back();
}
h.push_back(s[i]);
}
for (int i = (int)s.size() - 2, t = h.size(); i >= 0; i --) {
while (h.size() > t && cross(h.rbegin()[1], h.back(), s[i]) <= 0) {
h.pop_back();
}
h.push_back(s[i]);
}
if (h.size() > 1) {
h.pop_back();
}
return h;
}闵可夫斯基和
0x72 闵可夫斯基和.cpp:
// 闵可夫斯基和(默认:逆时针)
auto minkowski(std::vector<point> a, std::vector<point> b) {
if (a.size() <= 2 || b.size() <= 2) { // 若 a, b 均为凸壳,可以省去这一段特判
std::vector<point> c;
for (point p : a) for (point q : b) c.push_back(p + q);
return gethull(c);
}
std::vector<point> c{a[0] + b[0]};
a.push_back(a[0]), b.push_back(b[0]); // 若 a, b 均为凸壳,省去此行
for (int i = 0; i + 1 < a.size(); i ++) {
a[i] = a[i + 1] - a[i];
}
for (int i = 0; i + 1 < b.size(); i ++) {
b[i] = b[i + 1] - b[i];
}
a.pop_back(), b.pop_back();
c.resize(a.size() + b.size() + 1);
std::merge(a.begin(), a.end(), b.begin(), b.end(), c.begin() + 1, [] (point l, point r) {
return cross(l, r) > 0; // 若 a, b 均为顺时针凸包(或凸壳),改成 <0
});
for (int i = 1; i < c.size(); i ++) {
c[i] = c[i] + c[i - 1];
}
c.pop_back(); // 若 a, b 均为凸壳,省去此行
return c; // c 可能会共线,但不会重点
}