Cod sursa(job #391126)

Utilizator alexandru92alexandru alexandru92 Data 5 februarie 2010 08:44:30
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
/* 
 * File:   main.cpp
 * Author: virtualdemon
 *
 * Created on February 4, 2010, 9:25 PM
 */
#include <cstdio>
#include <vector>
#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 ( (p0.first*p1.second+p1.first*p2.second+p0.second*p2.first) >= (p2.first*p1.second+p2.second*p0.first+p1.first*p0.second) );
}
int main()
{
    pr p0, p;
    int n, i, j=0;
    freopen("infasuratoare.in", "rt", stdin );
    scanf("%d%lf%lf", &n, &p0.first, &p0.second );
    v.pb(p0);
    for( i=1; i < n; ++i )
    {
        scanf("%lf%lf", &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() );
    s.pb(v[0]);
    s.pb(v[1]);
    s.pb(v[2]);
    for( i=3; i < n; ++i )
    {
        for( j=s.size(); j >= 2 && cmp( s[j-2], s[j-1], v[i] ); --j )
            s.pp();
        s.pb(v[i]);
    }
    freopen("infasuratoare.out", "wt", stdout );
    printf("%d\n", n=s.size() );
    for( ; n; --n )
        printf( "%lf %lf\n", s[n-1].first, s[n-1].second );
    return 0;
}