Cod sursa(job #1644175)

Utilizator Vali_DeaconuVali Deaconu Vali_Deaconu Data 9 martie 2016 21:51:36
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
# include <cstdio>
# include <bitset>
# include <algorithm>

using namespace std;

FILE *fin = fopen("infasuratoare.in", "rt");
FILE *fout = fopen("infasuratoare.out", "wt");

const int EPS = 1e-12; // 1*10^(-12)
const int MAXN = 120005;

struct punct { double x, y; };

bitset<MAXN> viz;
punct v[MAXN];
int st[MAXN];
int n, k;

inline int cmps(double a, double b) {
    if (a+EPS<b) return 1;
    if (b+EPS<a) return -1;
    return 0;
}

bool cmp(const punct& a, const punct& b) {
    int tmp;

    tmp = cmps(a.x, b.x);

    if (tmp != 0)
        return (tmp == 1);

    return (cmps(a.y, b.y) == 1);
}

int semn(punct a, punct b, punct c) {
    double A, B, C;
    A = a.y - b.y;
    B = b.x - a.x;
    C = a.x * b.y - b.x * a.y;
    return cmps(A*c.x + B*c.y + C, 0);
}

void infasuratoare() {
    int inc, i;

    sort(v+1, v+n+1, cmp);

    st[1] = 1; // se initializeaza stiva cu primele 2 puncte
    st[2] = 2;
    k = 2;
    i = 3;
    viz[2] = 1;
    inc = 1;

    while (!viz[1]) { // nu s-a inchis infasuratoarea
        while (viz[i]) {
            if (i == n)
                inc = -1;
            i += inc;
        }

        while (k >= 2 && semn(v[st[k-1]], v[st[k]], v[i]) == -1) // daca se respecta proprietatea determinantului
            viz[st[k--]] = 0;

        st[++k] = i;
        viz[i] = 1;
    }
}

int main() {
    int i;

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

    infasuratoare();

    fprintf(fout, "%d\n", k-1);
    for (i=2; i<=k; ++i)
        fprintf(fout, "%lf %lf\n", v[st[i]].x, v[st[i]].y);
    return 0;
}