Cod sursa(job #1866005)

Utilizator GinguIonutGinguIonut GinguIonut Data 2 februarie 2017 14:47:55
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>

#define nMax 120001
#define pdd pair<double, double>
#define x first
#define y second
#define mkp make_pair

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

int n, top;
pdd pct[nMax], stck[nMax];

double cross_product(const pdd &a, const pdd &b, const pdd &c)
{
    return a.x*b.y + a.y*c.x + b.x*c.y - c.x*b.y - b.x*a.y - a.x*c.y;
}

int cmp(const pdd &a, const pdd&b)
{
    return cross_product(pct[1], a, b)<0;
}

int main()
{
    double a, b;
    fin>>n;
    for(int i=1; i<=n; i++)
    {
        fin>>a>>b;
        pct[i]=mkp(a, b);
    }

    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);

    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];
    }

    fout<<top<<'\n';
    for(int i=top; i>=1; i--)
        fout<<fixed<<setprecision(6)<<stck[i].x<<" "<<stck[i].y<<'\n';
}