Cod sursa(job #1826476)

Utilizator isav_costinVlad Costin Andrei isav_costin Data 10 decembrie 2016 14:56:56
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <cstdio>
#include <algorithm>
#include <cmath>

const double eps=1.e-12;

int n, h[120005];

struct POINT
{
    double x, y;
};

POINT LL, v[120005];

using namespace std;

double cp( POINT P1, POINT P2, POINT P3 )
{
    return (P2.x-P1.x)*(P3.y-P2.y)-(P2.y-P1.y)*(P3.x-P2.x);
}
int ccw( POINT P1, POINT P2, POINT P3 )
{
    double crossp=cp(P1,P2,P3);

    if( fabs(crossp)<eps )
        return 0;

    if( crossp>=eps )
        return 1;

    return -1;
}
bool cmp( POINT A, POINT B )
{
    int c=ccw(LL,A,B);

    if( c==1 )
        return 1;

    if( c==-1 )
        return 0;
}
void afis( int k )
{
    int i;

    printf( "%d\n", k );

    for( i=1;i<=k;i++ )
        printf( "%lf %lf\n", v[h[i]].x, v[h[i]].y );
}
void infasuratoare( )
{
    int top=1, i=2;

    h[0]=0;
    h[1]=1;

    while( i<=n )
    {
        if( ccw(v[h[top-1]],v[h[top]],v[i])>0 )
        {
            h[++top]=i;
            i++;
        }
        else
            top--;
    }

    afis(top);
}

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

    int i;

    scanf( "%d", &n );

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

        if( v[0].y-v[i].y>0 )
        {
            v[0].y=v[i].y;
            v[0].x=v[i].x;
        }
        else
            if( fabs(v[0].y-v[i].y)<eps && v[0].x-v[i].x>=eps )
                v[0].x=v[i].x;
    }

    LL.x=v[0].x;
    LL.y=v[0].y;

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

    infasuratoare();

    return 0;
}