Cod sursa(job #917737)

Utilizator PatrikStepan Patrik Patrik Data 18 martie 2013 12:00:45
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.96 kb
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    #define MAX 120001
    int N  , k , X[MAX];
    struct punct{double x , y;bool d;}P[MAX],st[MAX];
    bool comp(punct a , punct b)
    {
        if(a.y ==  b.y)return a.x<b.x;
        return a.y<b.y;
    }

    void citire();
    void solve();
    void tipar();
    void adauga(int i);
    bool det(punct a , punct b , punct c)
    {
        if(a.x*b.y+b.x*c.y+c.x*a.y-b.y*c.x-c.y*a.x-b.x*a.y > 0)
            return 1;
        return 0;
    }

    int main()
    {
        citire();
        solve();
        tipar();
        return 0;
    }

    void citire()
    {
        freopen("infasuratoare.in" , "r" , stdin );
        scanf("%d" , &N );
        for(int i = 1 ; i <= N ; ++i )
            scanf("%lf%lf" , &P[i].x , &P[i].y) ;
    }

    void solve()
    {
        sort(P+1,P+N+1,comp);
        st[1] = P[1];st[2] = P[2];X[1] = 1;X[2] = 2;k = 2;
        P[1].d = P[2].d = 1;
        for(int i = 3 ; i <= N ; ++i )
            adauga(i);
        for(int i = N ; i ; i--)
            if(!P[i].d)adauga(i);
        if(!det(st[k-1],st[k],st[1]))k--;
    }

    void adauga(int i)
    {
        if(det(st[k-1],st[k],P[i] ))
        {
            st[++k] = P[i];
            X[k] = i;
            P[i].d=1;
        }
                else
                {
                    P[X[k]].d = 0;
                    int j = k-1;
                    while(!det(st[j-1],st[j],P[i]) && j > 1)
                    {
                        P[X[j]].d=0;
                        j--;
                    }
                    st[j+1] = P[i];
                    k = j+1;
                    X[k] = i;
                    P[i].d = 1;
                }

    }

    void tipar()
    {
        freopen("infasuratoare.out" , "w" , stdout );
        printf("%d\n" , k);
       for(int i = 1 ; i <= k ; ++i )
            printf("%lf %lf\n" , st[i].x , st[i].y);
    }