Viết chương trình xây dựng bao lồi từ n điểm C++ (Convex Hull)

Thuật toán:

- Trước tiên ta loại bỏ các điểm trùng nhau

- Để xác định bao trên :

+ Sắp xếp các điểm theo thứ tự tăng dần
+ Tạo mảng bao trên và thêm 2 điểm đầu tiên

+ Tiếp tục thêm các điểm đồng thời kiểm tra liên tục nếu 3 điểm cuối (trong mảng bao) không tạo thành rẽ phải thì xóa điểm giữa

- Để xác định bao dưới:

+Sắp xếp các điểm theo thứ tự giảm dần và làm tương tự như bao trên

+Xóa điểm đầu và điểm cuối trong báo dưới để chèn vào sau bao trên

=> Convex Hull (theo chiều kim đồng hồ)

Ghi chú:

- Code đã được chấp nhận trên kattis: 

Code:

#include<bits/stdc++.h>

#define X first

#define Y second

using namespace std;

typedef pair<int, int> ii;

const int N= 1000111;

int f(ii a, ii b, ii c){    // f>0 => c|ab,  f<0 => ab|c

   

    return b.X*c.Y + a.X*b.Y + a.Y*c.X - b.X*a.Y - c.X*b.Y - c.Y*a.X;

}

vector<ii> HalfConvexHull(vector<ii> a){

    vector<ii> v;

    for(int i=0; i < a.size(); i++){

       

        while (v.size() >= 2 && f(v[v.size()-2], v[v.size()-1], a[i]) <= 0) // f <= 0 counter clockwise, f >= 0 clockwise

            v.pop_back();

       

        v.push_back(a[i]);

    }

    return v;

}

vector<ii> ConvexHull(set<ii> s){

   

    vector<ii> top(s.begin(), s.end());        

    top = HalfConvexHull(top);                  //top convex hull

   

    vector<ii> bot(s.rbegin(), s.rend());      

    bot = HalfConvexHull(bot);                  //bot convex hull

   

    top.insert(top.end(), bot.begin()+1, bot.end()-1);

    return top;                                         //convex hull

}

int main(){

    //input    

    int n;  cin >> n;

    set<ii> s;

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

       

        int x, y;   cin >> x >> y;

        s.insert(ii(x,y));  

    }

   

    //process

    vector<ii> v(s.begin(), s.end());

    if (s.size() > 1) v= ConvexHull(s);

       

    //output

    cout<<v.size()<<"\n";

    for(auto val : v) cout<<val.X<<" "<<val.Y<<"\n";

}

<