Cod sursa(job #1671268)

Utilizator Tiberiu02Tiberiu Musat Tiberiu02 Data 1 aprilie 2016 15:32:26
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
# include <cstdio>

# include <algorithm>

# define N 120000
# define EPS 0.00000001

using namespace std;

struct coord {
    double x, y;
} v[N], s[N];

inline double ang( struct coord a, struct coord b ) {
    return ( a.y - s[0].y ) * ( b.x - s[0].x ) > ( b.y - s[0].y ) * ( a.x - s[0].x );
}

inline int verif( int i, int j )
{
    double a=(s[i].y-s[i-1].y)*(v[j].x-s[i-1].x);
    double b=(v[j].y-s[i-1].y)*(s[i].x-s[i-1].x);
    return a<b;
}

int main() {
    FILE *fin = fopen( "infasuratoare.in", "r" ), *fout = fopen( "infasuratoare.out", "w" );

    int n, i, vf, l;

    fscanf( fin, "%d", &n );

    for ( i = 0; i < n; i ++ )
        fscanf( fin, "%lf%lf", &v[i].x, &v[i].y );

    s[0] = v[0];
    for ( i = 1; i < n; i ++ )
        if ( v[i].x < s[0].x ) {
            s[0] = v[i];
            l = i;
        }

    swap( v[l], v[0] );
    sort( v + 1, v + n, ang );

    vf = -1;
    for ( i = 0; i < n; i ++ ) {
        while ( vf > 1 && verif(vf, i) /* v[i].y - s[vf - 1].y ) * ( s[vf].x - s[vf - 1].x ) > ( s[vf].y - s[vf - 1].y ) * ( v[i].x - s[vf - 1].x )*/ )
            vf --;

        s[++ vf] = v[i];
    }

    fprintf( fout, "%d\n", vf + 1 );
    for ( i = vf; i >= 0; i -- )
        fprintf( fout, "%lf %lf\n", s[i].x, s[i].y );

    fclose( fin );
    fclose( fout );

    return 0;
}