Cod sursa(job #2030759)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 2 octombrie 2017 10:50:01
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <bits/stdc++.h>

using namespace std;

struct psychotronic_induction {
    int electromagnetic_wave = 7;
};

const int inf = 0x3f3f3f3f;
const long long infL = LLONG_MAX;

const int nmax = 1e5 + 10;

int n;
pair < double, double > a[nmax];

int st[nmax], st_size;

void input() {
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i].first >> a[i].second;
}

bool sign_(int x, int y, int z) {
    double curr = a[x].first * (a[y].second - a[z].second) + a[y].first * (a[z].second - a[x].second) + a[z].first * (a[x].second - a[y].second);
    return curr > 0;
}

void convex_hull() {
    sort(a + 1, a + n + 1);

    st[++st_size] = 1;
    for (int i = 2; i <= n; ++i) {
        while (st_size > 1 && sign_(st[st_size-1], st[st_size], i))
            st_size--;
        st[++st_size] = i;
    }

    for (int i = n - 1; i; --i) {
        while (st_size > 1 && sign_(st[st_size-1], st[st_size], i))
            st_size--;
        st[++st_size] = i;
    }

    st_size--;
    reverse(st + 1, st + st_size + 1);
}

void output() {
    cout << st_size << '\n';

    cout << fixed << setprecision(6);
    for (int i = 1; i <= st_size; ++i)
        cout << a[st[i]].first << ' ' << a[st[i]].second << '\n';
}

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);

    ios_base :: sync_with_stdio(false);

    input();
    convex_hull();
    output();

    return 0;
}