Cod sursa(job #370461)

Utilizator alexandru92alexandru alexandru92 Data 1 decembrie 2009 12:44:18
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 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, next, now;
vector< pr > v, convex_hull;
int main()
{int n, i, p;
double x, y, last=0, m ,m2;
bool *use;
    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();
    convex_hull.pb( start );
    while( true )
    {now=convex_hull.back(); next=start;
     m=11000000001;
        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 point is counterclockwise
                    m2+=2*M_PI;
                if( m2 < m && m2 > last )
                    m=m2, next=v[i], p=i;
            }
        if( next == start )
            break;
        convex_hull.pb( next );
        use[p]=true;
        last=m;
    }
    out.open("infasuratoare.out");
    out<<(n=convex_hull.size())<<'\n';
    for( n-=1; n >= 0; --n )
        out<<convex_hull[n].first<<' '<<convex_hull[n].second<<'\n';
    free(use);
    return 0;
}