Cod sursa(job #1163285)

Utilizator rares96cheseliRares Cheseli rares96cheseli Data 1 aprilie 2014 11:57:55
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

int N, k, pmin;
struct pct{ double x, y; }a[120002], st[120002];

double cp(const pct &A, const pct &B, const pct &C)
{ return (A.x*B.y+B.x*C.y+A.y*C.x-B.y*C.x-B.x*A.y-A.x*C.y); }

struct cmp
{
    bool operator()(const pct &A, const pct &B)const
    { return (cp(a[1], A, B)<0); }
};

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

int main()
{
    f>>N;
    for (int i=1; i<=N; ++i)
    {
        f>>a[i].x>>a[i].y;
        if (a[pmin].x>a[i].x) pmin=i;
            else if (a[pmin].x==a[i].x && a[i].y<a[pmin].y) pmin=i;
    }
    swap(a[1], a[pmin]);
    sort(a+2, a+N+1, cmp());

    conexhull();

    g<<fixed<<setprecision(6)<<k<<'\n';
    for (int i=1; i<=k; ++i)
        g<<st[i].x<<' '<<st[i].y<<'\n';

    return 0;
}