凸包

二维凸包

模版

Andrew \(O(n\cdot\log{n})\)Graham \(O(n\cdot\log{n})\)

代码

C++
{ 计算几何基础 }
int st[100005];
bool used[100005];
vector<Point> ConvexHull2D(vector<Point> &p) {
    sort(begin(p), end(p));
    int len = p.size(), top = 0;
    for (int i = 0 ; i < len ; i++) {
        used[i] = false;
    }
    st[++top] = 0;
    for (int i = 1 ; i < len ; i++) {
        while (top > 1 && sgn(cross(p[st[top]] - p[st[top - 1]], p[i] - p[st[top]])) <= 0) {
            used[st[top--]] = false;
        }
        used[i] = true;
        st[++top] = i;
    }
    int temp = top;
    for (int i = len - 2 ; i >= 0 ; i--) {
        if (used[i]) continue;
        while (top > temp && sgn(cross(p[st[top]] - p[st[top - 1]], p[i] - p[st[top]])) <= 0) {
            used[st[top--]] = false;
        }
        used[i] = true;
        st[++top] = i;
    }
    vector<Point> res;
    for (int i = 1 ; i <= top ; i++) {
        res.emplace_back(p[st[i]]);
    }
    return res;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<Point> a(n);
    for (int i = 0 ; i < n ; i++) {
        cin >> a[i];
    }
    auto b = ConvexHull2D(a);
    Tdouble ans = 0;
    int len = b.size();
    for (int i = 0 ; i < len - 1 ; i++) {
        ans += distance(b[i], b[i + 1]);
    }
    cout << fixed << setprecision(2) << ans << "\n";
    return 0;
}

代码

C++
{ 计算几何基础 }
int st[100005];
vector<Point> ConvexHull2D(vector<Point> &p) {
    sort(begin(p) + 1, end(p), [&](const Point &x, const Point &y) {
        Tdouble temp = cross(x - p[0], y - p[0]);
        if (sgn(temp) == 1) return true;
        return sgn(temp) == 0 && distance(x, p[0]) < distance(y, p[0]);
    });
    int len = p.size(), top = 0;
    st[++top] = 0;
    for (int i = 1 ; i < len ; i++) {
        while (top > 1 && sgn(cross(p[st[top - 1]] - p[st[top]], p[st[top]] - p[i])) <= 0) {
            top--;
        }
        st[++top] = i;
    }
    st[++top] = 0;
    vector<Point> res;
    for (int i = 1 ; i <= top ; i++) {
        res.emplace_back(p[st[i]]);
    }
    return res;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<Point> a(n);
    for (int i = 0 ; i < n ; i++) {
        cin >> a[i];
        if (a[i].y < a[0].y || (a[i].y == a[0].y && a[i].x < a[0].x)) {
            swap(a[i], a[0]);
        }
    }
    auto b = ConvexHull2D(a);
    Tdouble ans = 0;
    int len = b.size();
    for (int i = 0 ; i < len - 1 ; i++) {
        ans += distance(b[i], b[i + 1]);
    }
    cout << fixed << setprecision(2) << ans << "\n";
    return 0;
}

例题

P2742 [USACO5.1] 圈奶牛Fencing the Cows /【模板】二维凸包 - 洛谷

习题

洛谷P3829

P3829 [SHOI2012] 信用卡凸包 - 洛谷

给出 \(n\) 个圆角矩形, 问这 \(n\) 个矩形构成的凸包的周长.

代码

C++
{ 计算几何基础 }
{ 二维凸包 }
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    Tdouble a, b, r;
    cin >> n >> a >> b >> r;
    a -= 2 * r;
    b -= 2 * r;
    Tdouble L = sqrt(a * a + b * b) / 2;
    Tdouble phi = atan(a / b);
    vector<Point> c;
    for (int i = 0 ; i < n ; i++) {
        Tdouble x, y, theta;
        cin >> x >> y >> theta;
        {
            Tdouble dx = cos(theta + phi) * L;
            Tdouble dy = sin(theta + phi) * L;
            c.emplace_back(x + dx, y + dy);
            c.emplace_back(x - dx, y - dy);
        }
        {
            Tdouble dx = cos(theta - phi) * L;
            Tdouble dy = sin(theta - phi) * L;
            c.emplace_back(x + dx, y + dy);
            c.emplace_back(x - dx, y - dy);
        }
    }
    auto res = ConvexHull2D(c);
    Tdouble ans = 0;
    int len = res.size();
    for (int i = 0 ; i < len - 1 ; i++) {
        ans += distance(res[i], res[i + 1]);
    }
    cout << fixed << setprecision(2) << ans + 2 * PI * r << "\n";
    return 0;
}

三维凸包

模版

代码

C++
{ 计算几何基础 }
Face st[2005];
Face temp[2005];
bool vis[2005][2005];
vector<Face> ConvexHull3D(const vector<Point3D> &p) {
    int cnt = 2;
    temp[1] = {{p[0], 0}, {p[1], 1}, {p[2], 2}};
    temp[2] = {{p[2], 2}, {p[1], 1}, {p[0], 0}};
    int len = p.size();
    for (int i = 3, top = 0 ; i < len ; i++) {
        for (int j = 1, v ; j <= cnt ; j++) {
            if (!(v = temp[j].see(p[i]))) {
                st[++top] = temp[j];
            }
            for (int k = 0 ; k < 3 ; k++) {
                vis[temp[j][k]][temp[j][(k + 1) % 3]] = v;
            }
        }
        for (int j = 1 ; j <= cnt ; j++) {
            for (int k = 0 ; k < 3 ; k++) {
                int x = temp[j][k], y = temp[j][(k + 1) % 3];
                if (vis[x][y] && !vis[y][x]) {
                    st[++top] = {{p[x], x}, {p[y], y}, {p[i], i}};
                }
            }
        }
        for (int j = 1 ; j <= top ; j++) {
            temp[j] = st[j];
        }
        cnt = top;
        top = 0;
    }
    vector<Face> res;
    for (int i = 1 ; i <= cnt ; i++) {
        res.emplace_back(temp[i]);
    }
    return res;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<Point3D> a(n);
    for (int i = 0 ; i < n ; i++) {
        cin >> a[i];
        a[i].shake();
    }
    auto res = ConvexHull3D(a);
    Tdouble ans = 0;
    int len = res.size();
    for (int i = 0 ; i < len ; i++) {
        ans += res[i].area();
    }
    cout << fixed << setprecision(3) << ans << "\n";
    return 0;
}

例题

P4724 【模板】三维凸包 - 洛谷