Cod sursa(job #2822913)

Utilizator vansJos da pa perete vans Data 26 decembrie 2021 13:30:43
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <iostream>
#include <algorithm>
#include <iomanip>

using namespace std;

const int NMAX = 12e4;

typedef long double ld;

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

int n, ans[NMAX + 1], ansl;

inline ld crossProd(const pct A, const pct B, const pct C) {
    return -(A.x * B.y + C.x * A.y + B.x * C.y - C.x * B.y - A.x * C.y - B.x * A.y);
}

int main()
{
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);
    scanf("%d", &n);
    int firstPct = 1;
    for(int i = 1; i <= n; ++i) {
        scanf("%Le%Le", &a[i].x, &a[i].y);
        if(a[firstPct].y > a[i].y || (a[firstPct].y == a[i].y && a[firstPct].x > a[i].y))
            firstPct = i;
    }
    swap(a[firstPct], a[1]);
    sort(a + 2, a + n + 1, [](const pct A, const pct B) {
         return crossProd(a[1], A, B) > 0;
    });

    ans[++ansl] = 1, ans[++ansl] = 2;
    for(int i = 3; i <= n; ++i) {
        while(ansl >= 2 && crossProd(a[ans[ansl - 1]], a[ans[ansl]], a[i]) < 0)
            --ansl;
        ans[++ansl] = i;
    }
    printf("%d\n", ansl);
    for(int i = ansl; i; --i)
        cout << fixed << setprecision(12) << a[ans[i]].x << " " << a[ans[i]].y << "\n";
    return 0;
}