Cod sursa(job #2789349)

Utilizator vansJos da pa perete vans Data 27 octombrie 2021 14:12:31
Problema Infasuratoare convexa Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <bits/stdc++.h>

using namespace std;

typedef long double ld;

const int NMAX = 12e4;

struct pct {
    ld x, y;
} a[NMAX + 1];

int n;

inline ld crossProd(const pct X, const pct Y, const pct Z) {
    return (Y.y - X.y) * (Z.x - X.x) - (Y.x - X.x) * (Z.y - X.y);
}

inline int secondToLast(stack<int> ST) {
    ST.pop();
    return ST.top();
}

int main()
{
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);
    scanf("%d", &n);
    int firstPoint = 0;
    for(int i = 1; i <= n; ++i) {
        scanf("%Le%Le", &a[i].x, &a[i].y);
        if(!firstPoint || (a[i].x < a[firstPoint].x || (a[i].x == a[firstPoint].x && a[i].y < a[firstPoint].y)))
            firstPoint = i;
    }
    swap(a[firstPoint], a[1]);
    sort(a + 2, a + n + 1, [](const pct X, const pct Y) {
        return crossProd(a[1], X, Y) > 0;
    });
    stack<int> ans;
    ans.push(1), ans.push(2);
    for(int i = 3; i <= n; ++i) {
        while(ans.size() >= 2 && crossProd(a[secondToLast(ans)], a[ans.top()], a[i]) < 0)
            ans.pop();
        ans.push(i);
    }
    cout << ans.size() << "\n";
    while(!ans.empty())
        cout << fixed << setprecision(12) << a[ans.top()].x << " " << a[ans.top()].y << "\n",
        ans.pop();
    return 0;
}