Cod sursa(job #390939)

Utilizator alexandru92alexandru alexandru92 Data 4 februarie 2010 20:29:01
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
/* 
 * File:   main.cpp
 * Author: virtualdemon
 *
 * Created on February 4, 2010, 7:16 PM
 */
#include <vector>
#include <utility>
#include <fstream>
#include <cstdlib>
#include <algorithm>
#define pb push_back

/*
 * 
 */
using namespace std;
typedef pair< double, double > pr;
pr p0, p;
vector< pr > v, s;
inline bool cmp( pr p1, pr p2 )
{
    double x=(p1.first-p0.first)*(p2.second-p0.second), y=(p1.second-p0.second)*(p2.first-p0.first);
    return x < y;
}
inline bool check( pr p0, pr p1, pr p2 )
{
    return ( p0.first*p1.second+p1.first*p2.second+p0.second*p2.first - p1.second*p2.first-p2.second*p0.first-p1.first*p0.second ) >= 0;
}
int main()
{
    int n, i, j=0;
    ifstream in("infasuratoare.in");
    in>>n>>p0.first>>p0.second;
    v.pb(p0);
    for( i=1; i < n; ++i )
    {
        in>>p.first>>p.second;
        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(), cmp );
    s.pb(v[0]);
    s.pb(v[1]);
    s.pb(v[2]);
    for( i=3; i < n; ++i )
    {
        for( j=s.size(); j >= 2 && check( s[j-2], s[j-1], v[i] ); --j )
            s.pop_back();
        s.pb(v[i]);
    }
    ofstream out("infasuratoare.out");
    out<<(n=s.size())<<'\n';
    for( ; n; --n )
        out<<s[n-1].first<<' '<<s[n-1].second<<'\n';
    return 0;
}