Cod sursa(job #370566)

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

/*
 *
 */
using namespace std;
ifstream in;
ofstream out;
pr start, now, next;
vector< pr > v, convex_hull;
int main()
{bool *use;
 int n, i, p=0;
 double x, y, m, m2, last;
    in.open("infasuratoare.in");
    in>>n>>x>>y;
    use=(bool*)calloc( n, sizeof(bool) );
    start=mk( x, y );
    v.pb( start );
    n-=1;
    while( n-- )
    {
        in>>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 ) //if it's counterclokwise
                    m2+=2*M_PI;
                m2-=last;
                if( m2 < 0 )
                    m2+=2*M_PI;
                if( m2 < m )
                   m=m2, next=v[i], p=i;
            }
        if( next == start )
            break;
        convex_hull.pb( next );
        use[p]=true;
        last=m;
    }
    free(use);
    out.open("infasuratoare.out");
    out<<(n=convex_hull.size())<<'\n';
    for( ; n; --n )
        out<<convex_hull[n-1].first<<' '<<convex_hull[n-1].second<<'\n';
    return 0;
}