Cod sursa(job #390906)

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

/*
 * 
 */
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.second-p0.second)*(p2.first-p0.first), y=(p2.second-p0.second)*(p1.first-p0.first);
    if( x == y )
      return p1 < p2;
    return x < y;
}
inline bool check( pr p0, pr p1, pr p2 )
{
    return (p2.first-p0.first)*(p1.second-p0.second) > (p1.first-p0.first)*(p2.second-p0.second);
}
int main(int argc, char** argv)
{
    int n, i, j=0;
    ifstream in("infasuratoare.in");
    in>>n>>p0.first>>p0.second;
    v.push_back(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.push_back(p);
    }
    swap( v[0], v[j] );
    sort( v.begin()+1, v.end(), cmp );
    s.push_back(v[0]);
    s.push_back(v[1]);
    s.push_back(v[2]);
    for( i=3; i < n; ++i )
    {
        for( j=s.size()-1; j >= 2 && check( s[j-1], s[j], v[i] ); --j, s.pop_back() );
        s.push_back(v[i]);
    }
    ofstream out("infasuratoare.out");
    out<<s.size()<<'\n';
    for( i=0, n=s.size(); i < n; ++i )
        out<<s[i].first<<' '<<s[i].second<<'\n';
    return (EXIT_SUCCESS);
}