Cod sursa(job #2573985)

Utilizator IulianOleniucIulian Oleniuc IulianOleniuc Data 5 martie 2020 19:50:03
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda OJI 2020 Partea a II-a Marime 1.02 kb
#include <bits/stdc++.h>
using namespace std;

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

#define x first
#define y second
#define Point pair<double, double>

double cp(Point a, Point b, Point c) {
    return (b.y - a.y) * (c.x - a.x) - (b.x - a.x) * (c.y - a.y);
}

int main() {
    int n; fin >> n;
    vector<Point> pts(n);
    for (int i = 0; i < n; i++)
        fin >> pts[i].x >> pts[i].y;

    swap(pts.front(), *min_element(pts.begin(), pts.end()));
    sort(pts.begin() + 1, pts.end(), [&](Point a, Point b) {
        return cp(a, pts[0], b) < 0;
    });

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

    fout << fixed << setprecision(6) << st.size() << '\n';
    for (int i = st.size() - 1; i >= 0; i--)
        fout << st[i].x << ' ' << st[i].y << '\n';

    fout.close();
    return 0;
}