Cod sursa(job #1395287)

Utilizator Mr.DoomRaul Ignatus Mr.Doom Data 21 martie 2015 10:46:31
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;

#define x first
#define y second

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

const int Nmax = 120002;
using Punct = pair<double, double>;

int n, top;
Punct p[Nmax];
Punct A[Nmax];

void Read();
inline double CrossProduct(const Punct& A, const Punct& B, const Punct& C);
inline int Cmp(const Punct& p1, const Punct& p2);
void Sortare();
void Infasuratoare();
void Write();


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

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

void Read()
{
    is >> n;
    for ( int i = 1; 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) - (B.y - A.y) * (C.x - A.x);
}

inline int Cmp(const Punct& p1, const Punct& p2)
{
    return CrossProduct(p[1], p1, p2) > 0;
}

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

void Infasuratoare()
{
    Sortare();
    A[1] = p[1];
    A[2] = p[2];
    top = 2;
    for ( int i = 3; i <= n; ++i )
    {
        while ( top >= 2 && CrossProduct(A[top - 1], A[top], p[i]) < 0 )
            --top;
        A[++top] = p[i];
    }
}

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