Cod sursa(job #1504572)

Utilizator Corina1997Todoran Ana-Corina Corina1997 Data 17 octombrie 2015 21:52:04
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;

ifstream is("infasuratoare.in");
ofstream os("infasuratoare.out");

#define x second
#define y first

int n, top;
typedef pair<double, double> Pct;
#define MAX_N 120005
Pct v[MAX_N];
Pct stk[MAX_N];

void Read();
void ConvexHull();
void Write();
void SortPct();
inline double Cmp( const Pct& p1, const Pct& p2 );
inline double CrossProduct( const Pct& A, const Pct& B, const Pct& C );

int main()
{
    Read();
    ConvexHull();
    Write();

    is.close();
    os.close();
    return 0;
}

void Read()
{
    is >> n;
    for ( int i = 1; i <= n; i++ )
        is >> v[i].x >> v[i].y;
}

void ConvexHull()
{
    SortPct();
    stk[1] = v[1];
    stk[2] = v[2];
    top = 2;

    for( int i = 3; i <= n; i++ )
    {
        while( top >= 2 && CrossProduct(stk[top - 1], stk[top], v[i]) < 0 )
            top--;
        stk[++top] = v[i];
    }
}

void SortPct()
{
    int pos = 1;
    for ( int i = 2; i <= n; i++ )
        if ( v[i] < v[pos] )
            pos = i;
    swap( v[1], v[pos] );
    sort( v + 2, v + n + 1, Cmp );
}

inline double Cmp( const Pct& p1, const Pct& p2 )
{
    return CrossProduct( v[1], p1, p2 ) > 0;
}

inline double CrossProduct( const Pct& A, const Pct& B, const Pct& C )
{
    return (B.x - A.x)*(C.y - A.y) - (B.y - A.y)*(C.x - A.x);
}

void Write()
{
    os << fixed;
    os << top << '\n';
    for ( int i = 1; i <= top; i++ )
        os << setprecision(6) << stk[i].x << ' ' << stk[i].y << '\n';
}