Cod sursa(job #1246835)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 21 octombrie 2014 18:48:17
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include<fstream>
#include<algorithm>

using namespace std;

ifstream fin( "infasuratoare.in" );
ofstream fout( "infasuratoare.out" );

const int nmax = 120000;
int n, st[ nmax ];
struct pct{ double x, y; } v[ nmax ];

void read() {
    fin >> n;
    for( int i = 0; i < n; ++ i ) {
        fin >> v[ i ].x >> v[ i ].y;
    }
}
bool cmp( pct a, pct b ) {
    if ( a.x != b.x ) {
        return ( a.x < b.x );
    } else {
        return ( a.y < b.y );
    }
}
bool ccw( pct a, pct b, pct c ) {
    double X;
    X = ( a.y - b.y ) * c.x + ( b.x - a.x ) * c.y + b.y * a.x - a.y * b.x;
    if ( X > 0 ) {
        return 0;
    }
    return 1;
}
int main() {
    int ii;
    read();

    sort( v, v + n, cmp );
    ii = 2; st[ 0 ] = 0; st[ 1 ] = 1;
    for( int i = 2; i < n; ++ i ) {
        while ( ii > 2 && !ccw( v[ st[ ii - 2 ] ], v[ st[ ii - 1 ] ], v[ i ] ) ) {
            -- ii;
        }
        if ( ccw( v[ st[ ii - 2 ] ], v[ st[ ii - 1 ] ], v[ i ] ) ) {
            st[ ii ++ ] = i;
        } else {
            st[ ii - 1 ] = i;
        }
    }
    for( int i = n - 2; i >= 0; -- i ) {
        while ( ii > 2 && !ccw( v[ st[ ii - 2 ] ], v[ st[ ii - 1 ] ], v[ i ] ) ) {
            -- ii;
        }
        if ( ccw( v[ st[ ii - 2 ] ], v[ st[ ii - 1 ] ], v[ i ] ) ) {
            st[ ii ++ ] = i;
        } else {
            st[ ii - 1 ] = i;
        }
    }

    fout << ii - 1 << '\n';
    for( int i = 0; i < ii - 1; ++ i ) {
        fout << v[ st[ i ] ].x << ' ' << v[ st[ i ] ].y << '\n';
    }

    fin.close();
    fout.close();
    return 0;
}