Cod sursa(job #2756046)

Utilizator NanuGrancea Alexandru Nanu Data 29 mai 2021 11:39:50
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <math.h>

using namespace std;

ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");

#define DIM 120005

const double eps=1e-12;

int n, i, st[DIM], sel[DIM], vf, semn;
struct nanu {
    double x, y;
} v[DIM], pct;


static inline double det(nanu a, nanu b, nanu c) {
    return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}

static inline int cmp_pct(nanu p, nanu a, nanu b) {
    double d = det(pct, a, b);

    if(fabs(d) < eps)
        return 0;
    if(d  >= eps)
        return 1;
    return -1;
}

static inline bool cmp(nanu a, nanu b) {
    return (cmp_pct(pct, a, b) > 0);
}

int main() {
    cin >> n;
    cin >> v[1].x >> v[1].y;
    for(i = 2; i <= n; i++) {
        cin >> v[i].x >> v[i].y;
        if(v[i].y - v[1].y <= -eps || (fabs(v[i].y - v[1].y) < eps && v[i].x - v[1].x <= -eps))
            swap(v[1], v[i]);
    }

    pct = v[1];
    sort(v + 2, v + n + 1, cmp);

    st[++vf] = 1;   ///indicele primului punct;
    st[++vf] = 2;
    sel[2] = 1;

    i = 3, semn = 1;
    while(!sel[1]) {
        while(sel[i] != 0) {
            if(i == n)
                semn *= -1;
            i += semn;
        }

        while(vf >= 2 && cmp_pct(v[st[vf - 1]], v[st[vf]], v[i]) == -1)
            sel[st[vf--]] = 0;

        sel[i] = 1;
        st[++vf] = i;
    }

    cout << vf - 1 << '\n';
    for(i = 1; i < vf; i++)
        cout << fixed << setprecision(6) << v[st[i]].x << " " << v[st[i]].y << '\n';

    return 0;
}