Cod sursa(job #2051376)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 28 octombrie 2017 21:24:04
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <cstdio>
#include <algorithm>
#include <cmath>

FILE *fin = fopen("infasuratoare.in", "r"), *fout = fopen("infasuratoare.out", "w");

#define MAXN 120000

#define EPS 0.00000001

struct myc {
    double x, y;
    inline bool operator < (const myc &u) const {
        if (std::fabs(x - u.x) > EPS) return x < u.x;
        else return y < u.y;
    }
} v[MAXN + 1];

int st[MAXN + 1];

inline double arie(myc a, myc b, myc c) {
    return a.x * b.y - a.y * b.x + b.x * c.y - b.y * c.x + c.x * a.y - c.y * a.x;
}

int main() {
    int n;
    fscanf(fin, "%d", &n);

    for (int i = 1; i <= n; i++)
        fscanf(fin, "%lf%lf", &v[i].x, &v[i].y);

    std::sort(v + 1, v + n + 1);

    int vf = 0;
    for (int i = 1; i <= n; i++) {
        while (vf > 1 && arie(v[st[vf - 1]], v[st[vf]], v[i]) < EPS)
            vf--;
        st[++vf] = i;
    }
    int l = vf;
    for (int i = n - 1; i > 0; i--) {
        while (vf > l && arie(v[st[vf - 1]], v[st[vf]], v[i]) < EPS)
            vf--;
        if (i != 1)
            st[++vf] = i;
    }

    fprintf(fout, "%d\n", vf);
    for (int i = 1; i <= vf; i++)
        fprintf(fout, "%.8f %.8f\n", v[st[i]].x, v[st[i]].y);

    fclose(fin);
    fclose(fout);
    return 0;
}