CSES: Convex Hull => Hard

#include<bits/stdc++.h>

#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define Bye return 0
#define CodeTyper main
#define ll int long long

using namespace std;

struct point{
    int x = 0, y = 0;

    bool operator == (point other) const{
        return x == other.x && y == other.y;
    }
};

int i, j;
point pivot;

struct vec{
    int x = 0, y = 0;
    vec(int _x, int _y) : x(_x), y(_y){};
};

vec to_vec(point a, point b){
    return vec(b.x-a.x, b.y-a.y);
}

long long cross(vec a, vec b){
    return (a.x*1ll*b.y-a.y*1ll*b.x);
}

bool counter_clock_wise(point p, point q, point r){
    return cross(to_vec(p, q), to_vec(p, r))>=0;
}

long long dist(point a, point b){
    return a.x*1ll*a.x + b.y*1ll*b.y;
}

bool collinear(point p, point q, point r){
    return cross(to_vec(p, q), to_vec(q, r)) == 0;
}

bool angleCmp(point a, point b){
    if(collinear(pivot, a, b))
        return dist(pivot, a)<dist(pivot, b);

    vec d1(a.x - pivot.x, a.y - pivot.y);
    vec d2(b.x - pivot.x, b.y - pivot.y);

    return (atan2(d1.y, d1.x)-atan2(d2.y, d2.x))<0;
}


void solve() {
    ll n; cin>>n;
    vector<point> P(n);
    for (auto& i : P)
        cin>>i.x>>i.y;

    if(n<=3){
        cout<<n<<endl;
        for (auto i : P)
            cout<<i.x<<" "<<i.y<<endl;
        return;
    }

    j = 0;
    for (i = 0; i<n; i++)
        if(P[i].y<P[j].y || (P[i].y == P[j].y && P[i].x<P[j].x))
            j = i;

    swap(P[0], P[j]);
    pivot = P[0];

    sort(++P.begin(), P.end(), angleCmp);

    vector<point> S;
    S.push_back(P[0]);
    S.push_back(P[1]);
    S.push_back(P[2]);

    for (i = 3; i<n; i++){
        j = (int) S.size();

        while(j>2){
            if(counter_clock_wise(S[j-2], S[j-1], P[i]))
                break;
            S.pop_back();
            j--;
        }

        S.push_back(P[i]);
    }

    set<pair<int, int>> ans;
    for (auto i : S)
        ans.insert({i.x, i.y});

    cout<<ans.size()<<endl;
    for (auto i : ans)
        cout<<i.first<<" "<<i.second<<endl;
}

int CodeTyper()
{
    boost;
    solve();
    Bye;
}

/*
    'Think FIRST, then CODE.'
    'May the CODE be with YOU.'
    'We are PROGRAMMERS, we have NO LIFE!'
*/