Cod sursa(job #1112021)

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

using namespace std;

struct valiPair {
    double x, y, sinus;
} maxK, k;

long n;
double x, y;
bool pb;
vector<valiPair> q, v;



inline double myDistance ( valiPair p1, valiPair p2 ) {
    return sqrt ( ( p2.x - p1.x ) * ( p2.x - p1.x ) + ( p2.y - p1.y ) * ( p2.y - p1.y ) );
}

inline double sinus ( valiPair p1, valiPair p2 ) {
    if ( p1.x == p2.x && p1.y == p2.y ) return 2;
    else return ( p2.y - p1.y ) / myDistance ( p1, p2 );
}

bool cmp ( valiPair p1, valiPair p2 ) {
    return p1.sinus > p2.sinus;
}

inline bool leftTurn ( valiPair p1, valiPair p2, valiPair p3 ) {
    if ( p1.x == p2.x )
        return ( p2.y - p1.y ) * ( p2.x - p3.x ) > 0;
    else {
        double m = ( p2.y - p1.y ) / ( p2.x - p1.x ),
         n = p1.y - m * p1.x;
         return ( p2.x - p1.x ) * ( p3.y - ( m * p3.x + n ) ) > 0;
    }
}

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

    scanf ( "%ld", &n );
    maxK.x = maxK.y = 999999;

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

    for ( long i = 0; i < v.size ( ); i++ )
        v[i].sinus = sinus ( maxK, v[i] );

    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].x, q[i].y );

    return 0;
}