Cod sursa(job #3038051)

Utilizator PatrickvasileSoltan Cristian Patrickvasile Data 26 martie 2023 19:26:47
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.22 kb
#include <bits/stdc++.h>
//Soltan Cristian
#define fri(a, b) for (int i = (a); i < (b); ++i)
#define frj(a, b) for(int j = a; j < b; j++)
#define frk(a, b) for(int k = a; k < b; k++)
#define frm(a, b, i) for(int i = b; i >= a; i--)
#define ll long long
#define all(x) x.begin(), x.end()
#define mod 1000000007
#define pb push_back
#define st first
#define nd second
#define sz(x) (ll)x.size()
#define rall(x) x.rbegin(), x.rend()
#define ct(x) cout << x
#define cts(x) cout << x << ' '
#define ctn(x) cout << x << '\n'
#define Y cout << "YES" << '\n'
#define N cout << "NO" << '\n'
using namespace std;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vb = vector<bool>;
using ml = map<ll, ll>;
using vii = vector<vector<int>>;
using vll = vector<vector<ll>>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
template <typename T>void read(T n, vector<T> &a){fri(0, n){cin >> a[i];}}
template<typename T>void print(T n, T m, vector<vector<T>> &dp){fri(0, n){ct('\n');frj(0, m){ct(setw(5));cts(dp[i][j]);}}}



const int mxa = 1e6 + 1;
string __fname = "infasuratoare";  
ifstream in(__fname + ".in"); 
ofstream out (__fname + ".out"); 
#define cin in 
#define cout out

int orient(pair<int, int> a, pair<int, int> b, pair<int, int> c){
    ll v = a.st*(b.nd-c.nd)+b.st*(c.nd-a.nd)+c.st*(a.nd-b.nd);
    if (v < 0) return -1; // clockwise
    if (v > 0) return +1; // counter-clockwise
    return 0;

}

void solve(){
    int n;
    cin >> n;
    vector<pair<int, int>> a(n);
    fri(0, n){
        int x, y;
        cin >> x >> y;
        a[i] = {x, y};
    }
    sort(all(a));
    stack<pair<int, int>> s;
    s.push(a[0]);
    s.push(a[1]);
    for(int i = 2; i < n; i++){
        s.push(a[i]);
        pair<int, int> x, y;
        x = s.top();
        s.pop();
        y = s.top();
        s.pop();
        if(orient(s.top(), y, x) == 1){
            s.push(y);
            s.push(x);
        }
        // else if(orient(s.top(), y, x) == 0){
        //     s.push(y);
        //     s.push(x);
        // }
        else{
            s.push(x);
            while(sz(s) > 2){
                pair<int, int> w, e;
                e = s.top(); s.pop();
                w = s.top(); s.pop();
                if(orient(s.top(), w, e) == 1){
                    s.push(w);
                    s.push(e);
                    break;
                }
                // else if(orient(s.top(), w, e) == 0){
                //     s.push(w);
                //     s.push(e);
                //     break;
                // }
                else{
                    s.push(e);
                }
            }
        }
    }
    vector<pair<int, int>> ans;
    while(sz(s)){
        pair<int, int> w;
        w = s.top();
        s.pop();
        ans.pb(w);
    }
    reverse(all(ans));
    s.push(a[0]);
    s.push(a[1]);
    for(int i = 2; i < n; i++){
        s.push(a[i]);
        pair<int, int> x, y;
        x = s.top();
        s.pop();
        y = s.top();
        s.pop();
        if(orient(s.top(), y, x) == -1){
            s.push(y);
            s.push(x);
        }
        // else if(orient(s.top(), y, x) == 0){
        //     s.push(y);
        //     s.push(x);
        // }
        else{
            s.push(x);
            while(sz(s) > 2){
                pair<int, int> w, e;
                e = s.top(); s.pop();
                w = s.top(); s.pop();
                if(orient(s.top(), w, e) == -1){
                    s.push(w);
                    s.push(e);
                    break;
                }
                // else if(orient(s.top(), w, e) == 0){
                //     s.push(w);
                //     s.push(e);
                //     break;
                // }
                else{
                    s.push(e);
                }
            }
        }
    }
    s.pop();
    while(sz(s) > 1){
        pair<int, int> w;
        w = s.top();
        s.pop();
        ans.pb(w);
    }
    cout << sz(ans) << '\n';
    fri(0, sz(ans)){
        cout << ans[i].st << ' ' << ans[i].nd << '\n';
    }

}


int main()
{   
    ios_base::sync_with_stdio(0); cin.tie(0); ct(fixed); ct(setprecision(6)); 
    // int t;
    // cin >> t;
    // while(t--)
        solve();
    return 0;
}