Cod sursa(job #1512613)

Utilizator tudoras8tudoras8 tudoras8 Data 28 octombrie 2015 12:51:40
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <iomanip>

#define INF 0x3f3f3f3f
#define x first
#define y second

using namespace std;

typedef pair<double, double> point;

int n;
vector<point> v;

double cross_product(const point &O, const point &A, const point &B) {
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}

class my_stack : public stack<int> {
public:
    int top_second() {
        int x = top();
        pop();
        int result = top();
        push(x);
        return result;
    }
};

int main() {
#ifdef LOCAL
    freopen("input", "r", stdin);
#else
    ifstream cin("infasuratoare.in");
    ofstream cout("infasuratoare.out");
#endif // LOCAL

    cin >> n;
    int pos;
    point X = {INF, INF};
    for (int i = 0; i < n; ++i) {
        double x, y;
        cin >> x >> y;
        if (X.x > x || (X.x == x && X.y > y)) {
            X = {x, y};
            pos = i;
        }
        v.push_back({x, y});
    }

    swap(v[0], v[pos]);

    sort(v.begin() + 1, v.end(), [X](const point &A, const point &B) {
        return cross_product(X, A, B) < 0;
    });

    my_stack st;
    st.push(0);
    st.push(1);

    for (int i = 2; i < n; ++i) {
        if (st.size() >= 2 && cross_product(v[st.top_second()], v[st.top()], v[i]) > 0) {
            st.pop();
        }
        st.push(i);
    }

    cout << st.size() << '\n';
    cout << fixed << setprecision(6);
    while (!st.empty()) {
        point p = v[st.top()];
        st.pop();

        cout << p.x << ' ' << p.y << '\n';
    }

    return 0;
}