Cod sursa(job #1369238)

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

int N, pmin=1, vf;
struct asd{ double x, y;}a[120005], st[120005];
double crossedprod(asd A, asd B, asd C)
{
    return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}

double cmp(const asd &A, const asd &B)
{
    return crossedprod(a[1], A, B)<0;
}

void convexhull()
{
    st[++vf]=a[1]; st[++vf]=a[2];
    for (int i=3; i<=N; ++i)
    {
        while (vf>=2 && crossedprod(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);

    convexhull();

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