Cod sursa(job #370619)

Utilizator alexandru92alexandru alexandru92 Data 1 decembrie 2009 17:44:35
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.81 kb
/*
 * File:   main.cpp
 * Author: virtualdemon
 *
 * Created on November 28, 2009, 7:59 PM
 */
#include <cmath>
#include <vector>
#include <utility>
#include <cstdio>
#include <cstdlib>
#define pr pair< double, double>
#define pb push_back
#define mk make_pair< double, double >

/*
 *
 */
using namespace std;
pr start, next, now;
vector< pr > v, convex_hull;
int main()
{bool *use;
 int n, i, p;
 double x, y, m, m2, last;
    freopen("infasuratoare.in", "rt", stdin );
    scanf("%d %lf %lf",&n, &x, &y );
    use=(bool*)calloc( n, sizeof(bool) );
    start=mk( x, y );
    v.pb( start );
    n-=1;
    while( n-- )
    {
        scanf("%lf %lf", &x, &y );
        now=mk( x, y );
        if( y < start.second || ( y == start.second && x < start.first ) )
            start=now;
        
        v.pb( now );
    }
    n=v.size();
    last=0;
    convex_hull.pb( start );
    while( true )
    {next=start;
        now=convex_hull.back();
        m=1000001;
        for( i=0; i < n; ++i )
            if( !use[i] && now != v[i] )
            {
                m2=atan2( v[i].second-now.second, v[i].first-now.first );
                if( m2 < 0 )
                    m2+=2*M_PI;
                //m2-=last;
                //if( m2 < 0 )
                 //   m2+=2*M_PI;
                if(  m2 > last && m2 < m )
                    m=m2, next=v[i], p=i;
            }
        if( next == start )
            break;
        convex_hull.pb( next );
        use[p]=true;
        last=m;/*
        last=atan2( v[p].second-now.second, v[p].first-now.first );
        if( last < 0 )
            last+=2*M_PI; */
    }
    free(use);
    n=convex_hull.size();
    freopen( "infasuratoare.out", "wt", stdout );
    printf( "%d\n", n );
    for( i=0; i < n; ++i )
        printf( "%lf %lf\n", convex_hull[i].first, convex_hull[i].second );
    return 0;
}