Cod sursa(job #1676351)

Utilizator GinguIonutGinguIonut GinguIonut Data 5 aprilie 2016 20:57:35
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

#define pdd pair<double, double>
#define x first
#define y second
#define mkp make_pair
#define nMax 120003
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n, top;
pdd Pct[nMax], Stck[nMax];
void read()
{
    double a, b;
    fin>>n;

    for(int i=1;i<=n;i++)
    {
        fin>>a>>b;
        Pct[i]=mkp(a, b);
    }
}
double cross_product(const pdd& A, const pdd& B, const pdd& C)
{
    return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
inline bool cmp(const pdd& A, const pdd& B)
{
    return cross_product(Pct[1], A, B)<0;
}
void sort_points()
{
    int poz=1;
    for(int i=2;i<=n;i++)
    {
        if(Pct[i]<Pct[poz])
            poz=i;
    }
    swap(Pct[1], Pct[poz]);
    sort(Pct+2, Pct+n+1, cmp);
}
void solve()
{
    sort_points();

    Stck[++top]=Pct[1];
    Stck[++top]=Pct[2];

    for(int i=3;i<=n;i++)
    {
        while(top>=2 && cross_product(Stck[top-1], Stck[top], Pct[i])>0)
            top--;

        Stck[++top]=Pct[i];
    }
}
void write()
{
    fout<<top<<'\n';
    for(int i=top;i>=1;i--)
        fout<<fixed<<setprecision(6)<<Stck[i].x<<" "<<Stck[i].y
        <<'\n';
}
int main()
{
    read();
    solve();
    write();
    return 0;
}