monotonechain.cpp

Bài toán

Cho các điểm trên mặt phẳng, tìm bao lồi và tính diện tích của bao lồi

Độ phức tạp :

O(n log n)

Sắp xếp điểm theo góc : O(n log n)

Tìm bao lồi sau khi sắp xếp điểm : O(n)

Code này của : Đỗ Ngọc Khánh

#include <algorithm>

#include <cstdio>

#include <vector>

using namespace std;

const int N = 20000;

struct Point {

    long long x, y;

    bool operator<(const Point &v) const { return x == v.x ? y < v.y : x < v.x; }

    long long cross(const Point &p, const Point &q) const { return (p.x - x) * (q.y - y) - (p.y - y) * (q.x - x); }

} p[N], poly[N];

int n;

void enter() {

    scanf("%d", &n);

    for (int i = 0; i < n; ++i)

        scanf("%lld%lld", &p[i].x, &p[i].y);

}

long long size(Point poly[], int k) {

    long long S = (poly[k - 1].x - poly[0].x) * (poly[k - 1].y + poly[0].y);

    for (int i = 1; i < k; ++i)

        S += (poly[i - 1].x - poly[i].x) * (poly[i - 1].y + poly[i].y);

    return S;

    printf("%lld\n", S);

}

void solve() {

    sort(p, p + n);

    int k = 0;

    for (int i = 0; i < n; ++i) {

        while (k >= 2 && poly[k - 2].cross(poly[k - 1], p[i]) <= 0) --k;

        poly[k++] = p[i];

    }

    for (int i = n - 2, t = k + 1; i >= 0; --i) {

        while (k >= t && poly[k - 2].cross(poly[k - 1], p[i]) <= 0) --k;

        poly[k++] = p[i];

    }

    printf("%lld\n", size(poly, k));

}

int main() {

    enter();

    solve();

    return 0;

}

Nhận xét

Cảm ơn bạn Đỗ Ngọc Khánh đã cung cấp bài làm này.