Cod sursa(job #1968463)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 17 aprilie 2017 18:24:00
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

const int nmax = 12e4 + 10;

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

vector < int > st;

void input() {
    fin >> n;
    for (int i = 1; i <= n; ++i)
        fin >> p[i].x >> p[i].y;
}

int det(int a, int b, int c) {
    return p[a].x * (p[b].y - p[c].y) + p[b].x * (p[c].y - p[a].y) + p[c].x * (p[a].y - p[b].y);
}

bool out(int a, int b, int c) {
    return (det(a, b, c) < 0);
}

void run_convexhull() {
    sort(p + 1, p + n + 1);

    for (int i = 1; i <= n; ++i) {
        while (st.size() > 1 && out(st[st.size()-2], st[st.size()-1], i))
            st.pop_back();
        st.push_back(i);
    }

    for (int i = n - 1; i; --i) {
        while (st.size() > 1 && out(st[st.size()-2], st[st.size()-1], i))
            st.pop_back();
        st.push_back(i);
    }

    st.pop_back();
}

void output() {
    fout << fixed << setprecision(10);
    for (auto &it: st)
        fout << p[it].x << ' ' << p[it].y << '\n';
}

int main() {
    input();
    run_convexhull();
    output();

    return 0;
}