Cod sursa(job #2786394)

Utilizator UnknownPercentageBuca Mihnea-Vicentiu UnknownPercentage Data 20 octombrie 2021 20:54:17
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <bits/stdc++.h>

#define arr array <double, 2>

using namespace std;

inline void Open(const string Name) {
    #ifndef ONLINE_JUDGE
        (void)!freopen((Name + ".in").c_str(), "r", stdin);
        (void)!freopen((Name + ".out").c_str(), "w", stdout);
    #endif
}
    
const double EPS = 1e-12;

arr v[120001];

int vis[120001], st[120001];
int N, head;

double cross_prod(arr O, arr A, arr B) {
    return (A[0] - O[0]) * (B[1] - O[1]) - (B[0] - O[0]) * (A[1] - O[1]);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    Open("infasuratoare");

    cin >> N;
    for(int i = 1;i <= N;i++)
        cin >> v[i][0] >> v[i][1];

    sort(v + 1, v + N + 1);
    vis[2] = st[1] = 1, head = st[2] = 2;

    for(int i = 1, p = 1;i > 0;i += (p = (i == N? -p : p))) {
        if(vis[i] == 1) continue;
        while(head >= 2 && cross_prod(v[st[head - 1]], v[st[head]], v[i]) < EPS)
            vis[st[head--]] = 0;
        st[++head] = i;
        vis[i] = 1;
    }

    cout << head - 1 << "\n";
    cout << setprecision(6) << fixed;
    for(int i = 1;i < head;i++)
        cout << v[st[i]][0] << " " << v[st[i]][1] << "\n";

    return 0;
}