Cod sursa(job #800039)

Utilizator gallexdAlex Gabor gallexd Data 20 octombrie 2012 17:00:54
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

#define LMAX 120010

struct coord {
    double x,y;
};

int N;
coord puncte[LMAX];
int stack[LMAX], V;
bool viz[LMAX];

bool cmp(coord A, coord B) {
    if (A.x == B.x) {
        if (A.y < B.y) return true;
        return false;
    }
    if (A.x < B.x) return true;
    return false;
}

int semn(coord A, coord B, coord C) {
    return A.x*(B.y-C.y) + A.y*(C.x-B.x) + B.x*C.y - B.y*C.x;
}

void convex() {
    int step=1;
    stack[0]=0, stack[1]=1, V=1;
    viz[1]=true;

    for (int i=2; !viz[0];) {
        while (viz[i]) {
            if (i==N-1) step=-1;
            i+=step;
        }
        while (V>0 && semn(puncte[stack[V-1]], puncte[stack[V]], puncte[i])>0)
            viz[stack[V--]]=0;
        stack[++V]=i;
        viz[i]=true;
    }
}


int main () {

    double x,y;

    freopen("infasuratoare.in","rt",stdin);
    freopen("infasuratoare.out","wt",stdout);

    scanf("%d", &N);
    for (int i=0; i<N; ++i) {
        scanf("%lf %lf", &puncte[i].x, &puncte[i].y);
    }

    sort(puncte, puncte+N, cmp);

    convex();
    printf("%d\n", V);
    for(int i=0; i<V; ++i) {
        printf("%.6lf %.6lf\n", puncte[stack[i]].x, puncte[stack[i]].y);
    }
    return 0;
}