Cod sursa(job #1662165)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 24 martie 2016 15:43:12
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include<fstream>
#include<algorithm>
#include<vector>

using namespace std;

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

const int nmax = 120000;

struct pct{
    double x, y;

    inline bool operator < ( const pct &a ) const {
        if ( x != a.x ) {
            return ( x < a.x );
        }
        return ( y < a.y );
    }
} v[ nmax + 1 ];

pct st[ nmax + 1 ];
vector< pct > sol;

inline bool cw( pct a, pct b, pct c ) {
    return ( (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x) <= 0 );
}
int main() {
    int n;
    fin >> n;
    for( int i = 1; i <= n; ++ i ) {
        fin >> v[ i ].x >> v[ i ].y;
    }
    sort( v + 1, v + n + 1 );

    int t = 0;
    st[ ++ t ] = v[ 1 ];
    st[ ++ t ] = v[ 2 ];
    for( int i = 2; i <= n; ++ i ) {
        while ( t >= 2 && cw( st[ t - 1 ], st[ t ], v[ i ] ) ) {
            -- t;
        }
        st[ ++ t ] = v[ i ];
    }
    for( int i = 1; i <= t; ++ i ) {
        sol.push_back( st[ i ] );
    }

    t = 0;
    st[ ++ t ] = v[ n ];
    st[ ++ t ] = v[ n - 1 ];
    for( int i = n - 2; i > 0; -- i ) {
        while ( t >= 2 && cw( st[ t - 1 ], st[ t ], v[ i ] ) ) {
            -- t;
        }
        st[ ++ t ] = v[ i ];
    }

    for( int i = 2; i < t; ++ i ) {
        sol.push_back( st[ i ] );
    }

    fout << ( int )sol.size() << "\n";
    for( int i = 0; i < ( int )sol.size(); ++ i ) {
        fout << sol[ i ].x << " " << sol[ i ].y << "\n";
    }

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