Cod sursa(job #1098176)

Utilizator rares96cheseliRares Cheseli rares96cheseli Data 4 februarie 2014 16:45:17
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <algorithm>
#include <fstream>
#include <iomanip>
#define x first
#define y second
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

typedef pair<double, double> pct;
int N, top=2, pmin=1;
pct v[120005], st[120005];

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

inline int cmp(const pct& p1, const pct& p2) { return crossprod(v[1], p1, p2) < 0; }

void convexhull()
{
    st[1]=v[1]; st[2]=v[2];
    for (int i=3; i<=N; ++i)
    {
        while ( top>=2 && crossprod(st[top-1], st[top], v[i])>0 )
            --top;
        st[++top]=v[i];
    }

    g<<fixed<<setprecision(9)<<top<<'\n';
    for (int i=top; i; --i)
        g<<st[i].x<<' '<<st[i].y<<'\n';
}

void read()
{
    f>>N;
    for (int i=1; i<=N; ++i)
    {
        f>>v[i].x>>v[i].y;
        if (v[i]<v[pmin]) pmin=i;
    }
    swap(v[1], v[pmin]);
    sort(v+2, v+N+1, cmp);
}

int main()
{
    read();
    convexhull();
    return 0;
}