Cod sursa(job #883434)

Utilizator paul_gabryelPaul Buda paul_gabryel Data 20 februarie 2013 00:49:57
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb

#include <cstdio>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 120001;

#define x first
#define y second

pair<double,double> V[N];
vector<int> S;
int ind,n;

void READ ()
{

    ifstream in ("infasuratoare.in");

    in>>n;

    in>>V[0].x>>V[0].y;

    for( int i=1 ; i < n ; ++i )
    {
        in>>V[i].x>>V[i].y;
        if( V[i] < V[ind] )
            ind=i;
    }

}

bool CMP (const pair<double,double>& A, const pair<double,double>& B)
{
    return ( (A.x-V[0].x)*(B.y-V[0].y) < (B.x-V[0].x)*(A.y-V[0].y) );
}

bool ok (int i,int j,int k)
{
    return ( ( (V[j].x-V[i].x)*(V[k].y-V[i].y) - (V[j].y-V[i].y)*(V[k].x-V[i].x) ) > 0 ) ;
}

void SOLVE ()
{

    swap ( V[0] , V[ind] );

    sort ( V+1 , V+n , CMP );

    S.push_back( 0 );
    S.push_back( 1 );

    for( int i=2 ; i < n ; ++i )
    {

        for( ; S.size() > 2 && ok( S[S.size()-2] , S[S.size()-1] , i ) ; S.pop_back() );

        S.push_back( i );

    }

}

void OUT ()
{

    freopen ("infasuratoare.out","w",stdout);

    printf("%d\n",S.size());

    for( vector<int>::iterator I=S.end()-1 ; I >= S.begin() ; --I )
        printf("%lf %lf\n",V[*I].x,V[*I].y);

}

int main ()
{

    READ ();
    SOLVE ();
    OUT ();

    return 0;
}