graham.cpp

Bài toán

Tìm bao lồi của một danh sách điểm trên mặt phẳng

Độ phức tạp

O(n logn)

Code này của : Nguyễn Tiến Trung Kiên

#include <stdio.h>

#include <algorithm>

#include <iostream>

#include <vector>

using namespace std;

typedef vector<int> vi;

typedef long long int64;

#define int int64

struct vertex {

    int X, Y;

    void operator-=(vertex v) {

        X -= v.X;

        Y -= v.Y;

    }

    bool operator>(vertex v) {

        if (v.Y == Y)

            return X > v.X;

        else

            return Y > v.Y;

    }

};

class halfStack : public vi {

   public:

    void pop() { pop_back(); }

    void push(int v) { push_back(v); }

    int below() { return at(size() - 2); }

    int top() { return at(size() - 1); }

};

vertex a[23997];

int n;

halfStack hs;

int64 ccw(vertex w, vertex u, vertex v) {

    u -= w;

    v -= w;

    return (int64)u.X * v.Y - (int64)u.Y * v.X;

}

bool cmp(vertex u, vertex v) { return ccw(a[1], u, v) > 0; }

int64 lllabs(int64 a) { return a > 0 ? a : -a; }

void graham() {

    int k = 1;

    while (k <= n + 1) {

        if (hs.size() < 2)

            hs.push(k++);

        else {

            if (ccw(a[hs.below()], a[hs.top()], a[k]) <= 0)

                hs.pop();

            else

                hs.push(k++);

        }

    }

}

main() {

    //scanf("%d", &n);

    cin >> n;

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

        cin >> a[i].X >> a[i].Y;

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

        if (a[i] > a[1]) {

            vertex z = a[i];

            a[i] = a[1];

            a[1] = z;

        }

    sort(a + 2, a + n + 1, cmp);

    a[n + 1] = a[1];

    graham();

    int64 r = 0;

    for (int i = 0; i < hs.size() - 1; i++)

        r += (a[hs[i]].X - a[hs[i + 1]].X) * (a[hs[i]].Y + a[hs[i + 1]].Y);

    cout << lllabs(r) << endl;

}

Nhận xét