Cod sursa(job #1414005)

Utilizator rares96cheseliRares Cheseli rares96cheseli Data 2 aprilie 2015 11:44:11
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

int N, vf=2, pmin=1;
struct asd{ double x, y; }a[120005], st[120005];
double crossed_prod(asd A, asd B, asd C)
{
    return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}
struct cmp
{
    bool operator()(const asd &A, const asd &B)const
    {
        return crossed_prod(a[1], A, B)<0;
    }
};

void go()
{
    st[1]=a[1]; st[2]=a[2];
    for (int i=3; i<=N; ++i)
    {
        while (vf>=2 && crossed_prod(st[vf-1], st[vf], a[i])>0)
            --vf;
        st[++vf]=a[i];
    }
}

int main()
{
    f>>N;
    for (int i=1; i<=N; ++i)
    {
        f>>a[i].x>>a[i].y;
        if (a[i].x<a[pmin].x) pmin=i;
            else if (a[i].x==a[pmin].x && a[i].y<a[pmin].y)
                pmin=i;
    }
    swap(a[1], a[pmin]);
    sort(a+2, a+N+1, cmp());
    g<<fixed<<setprecision(6);
    go();
    g<<vf<<'\n';
    for (int i=vf; i; --i)
        g<<st[i].x<<' '<<st[i].y<<'\n';
    return 0;
}