Cod sursa(job #1112005)

Utilizator valiro21Valentin Rosca valiro21 Data 19 februarie 2014 12:31:55
Problema Infasuratoare convexa Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.86 kb
#include <cstdio>
#include <map>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

long n;
double x, y;
bool pb;
vector<pair<double, double> > q, v;
pair<double, double> maxP ( 99999, 99999 );

inline double myDistance ( pair<double, double> p1, pair<double, double> p2 ) {
    return sqrt ( pow ( p2.first - p1.first, 2 ) + pow ( p2.second - p1.second, 2 ) );
}

inline double sinus ( pair<double, double> p1, pair<double, double> p2 ) {
    if ( p1 == p2 ) return 2;
    else
        return ( p2.second - p1.second ) / myDistance ( p1, p2 );
}

bool cmp ( pair<double, double> p1, pair<double, double> p2 ) {
    return sinus ( maxP, p1 ) > sinus ( maxP, p2 );
}

inline bool leftTurn ( pair<double, double> p1, pair<double, double> p2, pair<double, double> p3 ) {
    if ( p1.first == p2.first )
        return ( p2.second - p1.second ) * ( p2.first - p3.first ) > 0;
    else {
        double m = ( p2.second - p1.second ) / ( p2.first - p1.first ),
         n = p1.second - m * p1.first;
         return ( p2.first - p1.first ) * ( p3.second - ( m * p3.first + n ) ) > 0;
    }
}

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

    scanf ( "%ld", &n );

    for ( long i = 1; i <= n; i++ ) {
        scanf ("%lf %lf", &x, &y),
        v.push_back ( make_pair ( x, y ) );
        if ( v.back ( ) < maxP )
            maxP = v.back ( );
    }

    sort ( v.begin ( ), v.end ( ), cmp );
    for ( long i = 0; i < v.size ( ); i++ ) {
        while ( q.size ( ) > 1 && leftTurn ( q[q.size ( ) - 2], q[q.size ( ) - 1], v[i] ) )
            q.pop_back ( );
        q.push_back ( v[i] );
    }

    printf ( "%ld\n", q.size ( ) );
    for ( long i = q.size ( ) - 1; i >= 0; i-- )
        printf ( "%lf %lf\n", q[i].first, q[i].second);

    return 0;
}