Cod sursa(job #367951)

Utilizator alexandru92alexandru alexandru92 Data 23 noiembrie 2009 20:24:04
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
/* 
 * File:   main.cpp
 * Author: virtualdemon
 *
 * Created on November 22, 2009, 3:40 PM
 */
#include <cmath>
#include <vector>
#include <utility>
#include <fstream>
#define pb push_back
#define mk make_pair< double, double >

/*
 *
 */
using namespace std;
ifstream in;
ofstream out;
vector< pair< double, double > > v, convex_hull;
vector< pair< double, double > >::iterator it, iend, start, next, now;
int main()
{int n;
 double x, y, maxim, maxim2;
    in.open("infasuratoare.in");
    in>>n;
    while( n-- )
    {
        in>>x>>y;
        v.pb( mk( x, y ) );
    }
    for( start=v.begin(), it=start+1, iend=v.end(); it < iend; ++it )
        if( it->first < start->first )
            start=it;
        else if( it->first == start->first && it->second < start->second )
                start=it;
    convex_hull.pb( *start );
    while( !v.empty() )
    {now=convex_hull.begin()-1; next=v.begin();
        maxim=atan2( next->first - now->first, next->second - now->second )+2*M_PI;
        for( it=next+1, iend=v.end(); it < iend; ++it )
        {
            maxim2=atan2( it->first - now->first, it->second - now->second )+2*M_PI;
            if( maxim2 > maxim )
                next=it, maxim=maxim2;
        }
        if( start->first == next->first && start->second == next->second )
            break;
        convex_hull.pb( *next );
        v.erase( next );
    }
    out.open("infasuratoare.out");
    n=convex_hull.size();
    out<<n<<'\n';
    for( n-=1; n >= 0; --n )
        out<<convex_hull[n].first<<' '<<convex_hull[n].second<<'\n';
    return 0;
}