Cod sursa(job #913089)

Utilizator avram_florinavram florin constantin avram_florin Data 13 martie 2013 09:12:36
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include<fstream>
#include<cstdio>
#include<vector>
#include<algorithm>
 
using namespace std;
 
const int MaxN = 120005;
 
struct punct{
        double x,y;
        }p[MaxN];
int n,vfs,st[2*MaxN];
vector<punct> Vans;
 
struct cmp
{
    bool operator()( const punct &a,const punct &b )
    {
        if( a.x != b.x )
            return a.x < b.x;
        return a.y < b.y;
    }
};
 
double sarrus(punct a , punct b , punct c)
{
    return a.x*b.y + b.x*c.y + c.x*a.y - b.y*c.x - b.x*a.y - a.x*c.y;
}
 
int main()
{
    freopen("infasuratoare.in" , "r" , stdin);
    freopen("infasuratoare.out" , "w" , stdout);
    scanf("%d" , &n);
    int i;
    for( i = 1 ; i <= n ; i++ )
        scanf("%lf%lf" , &p[i].x , &p[i].y);
    sort(p+1,p+n+1,cmp());
    vfs = 1; st[vfs] = 1;
    st[++vfs] = 2;
    for( i = 3 ; i <= n ; i++ )
        {
            while( vfs > 1 && sarrus(p[st[vfs-1]],p[st[vfs]],p[i]) < 0 )
                vfs--;
            st[++vfs] = i;
        }
    for( i = 1 ; i <= vfs ; i++ )
        Vans.push_back(p[st[i]]);
    vfs = 1; st[vfs] = n;
    st[++vfs] = n-1;
    for( i = n-2 ; i ; i-- )
        {
            while( vfs > 1 && sarrus(p[st[vfs-1]] , p[st[vfs]] , p[i]) < 0 )
                vfs--;
            st[++vfs] = i;
        }
    for( i = 2 ; i < vfs ; i++ )
        Vans.push_back(p[st[i]]);
    vector<punct>::iterator it,iend;
    iend = Vans.end();
    it = Vans.begin();
    printf("%d\n" , Vans.size());
    for( ; it != iend ; ++it )
        printf("%lf %lf\n" , it->x , it-> y);
    return 0;
}