Cod sursa(job #1370382)

Utilizator hanganflorinHangan Florin hanganflorin Data 3 martie 2015 14:13:10
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#define x second
#define y first
#define MAX 120002
using namespace std;

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

typedef pair<double, double> Punct;

Punct P[MAX];
Punct V[MAX];
int n, top = 1;

void Read();
void Sortare();
void Write();
inline double CrossProduct(const Punct& A, const Punct& B, const Punct& C );
inline bool Cmp(const Punct& P1, const Punct& P2);
void Invelitoare();

int main()
{
    Read();
    Sortare();
    Invelitoare();
    Write();
    is.close();
    os.close();
    return 0;
}
void Read()
{
    is >> n;
    for ( int i = 0; i < n; ++i )
        is >> P[i].x >> P[i].y;
}
inline double CrossProduct(const Punct& A, const Punct& B, const Punct& C )
{
    return (B.x-A.x)*(C.y-A.y) - (C.x-A.x)*(B.y-A.y);
}
void Sortare()
{
    int poz = 0;
    for ( int i = 1; i < n; ++i )
        if ( P[i] < P[poz] )
            poz = i;
    swap(P[0], P[poz]);
    sort(P+1, P+n, Cmp );
}
inline bool Cmp(const Punct& P1, const Punct& P2)
{
    return CrossProduct(P[0], P1, P2) > 0;
}
void Write()
{
    //for ( int i = 0; i < n; ++i )
    //    os << P[i].x << ' ' << P[i].y << '\n';
    os << top+1 << '\n';
    for ( int i = 0; i <= top; ++i )
        os << fixed << setprecision(6) << V[i].x << ' ' << V[i].y << '\n';
}
void Invelitoare()
{
    V[0] = P[0];
    V[1] = P[1];
    for ( int i = 2; i < n; ++i )
    {
        while ( top >= 1 && CrossProduct(V[top-1], V[top], P[i]) < 0 )
            top--;
        V[++top] = P[i];
    }
}