Cod sursa(job #3226924)

Utilizator alexdumitruAlexandru Dumitru alexdumitru Data 23 aprilie 2024 12:18:41
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 120000;

struct Point {
    double x, y;
};

int n;
Point a[NMAX + 1];

bool cmp(const Point & a, const Point & b) {
    if (a.x != b.x)
        return a.x < b.x;
    return a.y < b.y;
}

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

int st[NMAX + 5];
bool in[NMAX + 1];

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

    sort(a + 1, a + n + 1, cmp);

    int sz = 2;
    st[1] = 1; st[2] = 2;
    in[2] = 1;

    for (int i = 3; i <= n; i++) {
        while (sz >= 2 && det(a[st[sz - 1]], a[st[sz]], a[i]) >= 0) {
            in[st[sz]] = 0;
            sz--;
        }
        st[++sz] = i;
        in[i] = 1;
    }

    for (int i = n; i >= 1; i--) {
        if (!in[i]) {
            while (sz >= 2 && det(a[st[sz - 1]], a[st[sz]], a[i]) >= 0) {
                in[st[sz]] = 0;
                sz--;
            }
            st[++sz] = i;
            in[i] = 1;
        }
    }
    sz--;

    fout << sz << '\n';
    fout << fixed << setprecision(12);
    for (int i = sz; i >= 1; i--) {
        fout << a[st[i]].x << ' ' << a[st[i]].y << '\n';
    }
}

signed main() {
    solve();
    return 0;
}