「v4」0x70 计算几何

    「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 可能会共线,但不会重点
    }