Cod sursa(job #1119571)

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

    bool det(punct p1 , punct p2 , punct p3 )
    {
        return p1.x*p2.y+p2.x*p3.y+p3.x*p1.y-p2.y*p3.x-p3.y*p1.x-p2.x*p1.y > 0;
    }


    void read();
    void solve();
    void write();
    void add(int x);

    int main()
    {
        read();
        solve();
        write();
        return 0;
    }

    void read()
    {
        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 , f);
        for(int i = 1 ; i<= N ; ++i )
            add(i);
        for(int i = N ; i ; i--)
            if(!P[i].d)add(i);
        if(!det(P[st[k-1]],P[st[k]],P[st[1]]))k--;
    }

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

    void add(int x)
    {
        if(k < 2){
            st[++k] = x;
            P[x].d = 1;}
        else
        {
            st[++k] = x;
            P[x].d = 1;
            while(k > 2 && !det(P[st[k-2]],P[st[k-1]],P[st[k]]))
            {
                P[st[k-1]].d = 0;
                st[k-1] = st[k];
                k--;
            }
        }
    }