Cod sursa(job #2822909)

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

using namespace std;

typedef long double ld;

const int NMAX = 12e4;

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

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

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);
    return -(X.x * Y.y + Z.x * X.y + Y.x * Z.y - Z.x * Y.y - X.x * Z.y - Y.x * X.y);
}

int main()
{
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);
    scanf("%d", &n);
    int firstPoint = 1;
    for(int i = 1; i <= n; ++i) {
        scanf("%Le%Le", &a[i].x, &a[i].y);
        if(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;
    });
    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;
    }
    cout << ansl << "\n";
    while(ansl)
        cout << fixed << setprecision(12) << a[ans[ansl]].x << " " << a[ans[ansl]].y << "\n",
        --ansl;
    return 0;
}