Cod sursa(job #899194)

Utilizator stay_awake77Cangea Catalina stay_awake77 Data 28 februarie 2013 13:16:51
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <cstdio>
#include <algorithm>

#define NMAX 120005
#define PDD pair< double, double >
#define x first
#define y second

using namespace std;

int N, i, sens, Lg;
PDD P[NMAX];
bool Used[NMAX];
int Stack[NMAX];

inline double Semn( PDD A, PDD B, PDD C )
{
    return A.x*B.y + B.x*C.y + C.x*A.y - B.y*C.x - C.y*A.x - A.y*B.x;
}

int main()
{
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);

    scanf("%d", &N);
    for( i = 1; i <= N; ++i )
        scanf("%lf%lf", &P[i].x, &P[i].y );

    sort( P + 1, P + N + 1 );

    Stack[1] = 1;
    Stack[2] = 2; Used[2] = true;
    Lg = 2;
    i = 3;
    sens = 1;

    while( !Used[1] )
    {
        while( Used[i] )
        {
            if( i == N ) sens = -1;
            i += sens;
        }

        while( Lg > 1 && Semn( P[Stack[Lg - 1]], P[Stack[Lg]], P[i] ) < 0 )
            Used[ Stack[Lg--] ] = false;

        Stack[++Lg] = i;
        Used[i] = true;
    }

    Lg--;
    printf("%d\n", Lg);
    for( i = 2; i <= Lg + 1; ++i )
        printf("%.6lf %.6lf\n", P[Stack[i]].x, P[Stack[i]].y);

    return 0;
}