Cod sursa(job #1058049)

Utilizator valiro21Valentin Rosca valiro21 Data 14 decembrie 2013 23:52:13
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.15 kb
#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

#define P pair<double, double>
#define pb push_back

vector<P> queue,v;
P m;
long n, ind;
double x, y;

double dist ( P a, P b ) {
    double x = b.first - a.first, y = b.second - a.first;
    x *= x; y *= y;
    return sqrt ( x + y );
}

double sin ( P source, P a ) {
    if ( source.first == a.first )
        return 1;
    double sin = ( a.second - source.second ) / dist ( source, a );
    return sin;
}

bool rightOfLine ( P a, P b, P c ) {
    if ( a.first == b.first )
        if ( b.second - a.second > 0 )
            return c.first >= a.first;
        else
            return c.first < a.first;

    if ( a.second == b.second )
        if ( b.first - a.first > 0 )
            return c.second <= a.second;
        else
            return c.second > a.second;


    double p = ( a.second - b.second ) / ( a.first - b.first ), d = a.second - a.first * p;
    double x = ( c.second - d ) / p;

    if ( b.second - a.second > 0 ) {
        if ( x < c.first )
            return 1;
    }
    else if ( x > c.first )
        return 1;

    return 0;
}

bool comp ( P a, P b ) {
    return sin ( m, a ) >= sin ( m, b );
}

int main()
{
    freopen ( "infasuratoare.in", "rt", stdin );
    freopen ( "infasuratoare.out", "wt", stdout );

    scanf ( "%ld", &n );
    scanf ( "%lf %lf", &m.first, &m.second );
    for ( long i = 2; i <= n; i++ ) {
        scanf ( "%lf %lf", &x, &y );

        if ( x < m.first || ( x == m.first && y < m.second ) ) {
            v.pb ( m );
            m.first = x; m.second = y;
        }
        else
            v.pb ( make_pair ( x, y ) );
    }

    sort ( v.begin ( ), v.end ( ), comp );
    queue.pb ( m );queue.pb ( v[0] );ind = 1;

    while ( ind < n - 1 ) {
        while ( queue.size () > 1 && !rightOfLine ( queue[queue.size ( ) - 2], queue[queue.size ( ) - 1], v[ind] ) )
            queue.pop_back ( );

        queue.push_back ( v[ind] );
        ind++;
    }

    printf ( "%ld\n", queue.size ( ) );
    for ( long i = 0; i < queue.size ( ); i++ )
        printf ( "%lf %lf\n", queue[i].first, queue[i].second );

    return 0;
}