Cod sursa(job #391006)

Utilizator alexandru92alexandru alexandru92 Data 4 februarie 2010 21:52:39
Problema Infasuratoare convexa Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
/* 
 * File:   main.cpp
 * Author: virtualdemon
 *
 * Created on February 4, 2010, 9:25 PM
 */
#include <vector>
#include <fstream>
#include <iterator>
#include <algorithm>
#define pp pop_back
#define pb push_back

/*
 *
 */
using namespace std;
struct pr
{
    double first, second;
};
vector< pr > v, s;
inline void swap( pr& a, pr& b )
{
    pr aux=a;
    a=b;
    b=aux;
}
inline bool operator<( pr p1, pr p2 )
{
    return (p1.first-v[0].first)*(p2.second-v[0].second) > (p1.second-v[0].second)*(p2.first-v[0].first);
}
inline bool cmp( pr p0, pr p1, pr p2 )
{
    return ( ( (p2.first-p0.first)*(p1.second-p0.second) ) > ( (p2.second-p0.second)*(p1.first-p0.first) ) );
}
inline istream& operator>>( istream& in, pr& x )
{
    in>>x.first>>x.second;
    return in;
}
inline ostream& operator<<( ostream& out, pr x )
{
    out<<x.first<<' '<<x.second<<'\n';
    return out;
}
int main()
{
    pr p, p0;
    int n, i, j=0;
    ifstream in("infasuratoare.in");
    in>>n>>p0;
    v.pb(p0);
    for( i=1; i < n; ++i )
    {
        in>>p;
        if( p.second < p0.second || (p.second == p0.second && p.first < p0.first ) )
            p0=p, j=i;
        v.pb(p);
    }
    swap( v[0], v[j] );
    sort( v.begin()+1, v.end() );
    s.pb(v[0]);
    s.pb(v[1]);
    s.pb(v[2]);
    for( i=3; i < n; ++i )
    {
        for( j=s.size()-1; j > 2 && cmp( s[j-1], s[j], v[i] ); --j, s.pp() );
        s.pb(v[i]);
    }
    ofstream out("infasuratoare.out");
    out<<s.size()<<'\n';
    copy( s.begin(), s.end(), ostream_iterator<pr>(out) );
    return 0;
}