Cod sursa(job #1813986)

Utilizator caprariuapCaprariu Alin-Paul caprariuap Data 23 noiembrie 2016 16:08:17
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <algorithm>
#include <iomanip>
#include <fstream>

using namespace std;

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

struct punct{
    double x,y;
} v[130000],s[130000],minim;

double cp(punct a, punct b, punct c)
{
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}

bool cmp(punct a, punct b)
{
    return cp(v[1],a,b)<0;
}

int n,i,j,poz,vf;

int main()
{
    fin>>n;
    i=1;
    fin>>v[1].x>>v[1].y;
    minim.x=v[1].x;
    minim.y=v[1].y;
    poz=1;
    for (i=2; i<=n; i++)
    {
        fin>>v[i].x>>v[i].y;
        if (v[i].x<minim.x||(v[i].x==minim.x&&v[i].y<minim.y))
            minim.x=v[i].x,minim.y=v[i].y,poz=i;
    }
    swap(v[1],v[poz]);
    sort(v+2,v+n+1,cmp);
    s[1]=v[1];
    s[2]=v[2];
    vf=2;
    for (i=3; i<=n; i++)
        {
            while (vf>=2&&cp(s[vf-1],s[vf],v[i])>0)
                vf--;
            s[++vf]=v[i];
        }
    fout<<vf<<'\n';
    for (i=vf; i; i--)
        fout<<fixed<<setprecision(9)<<s[i].x<<' '<<s[i].y<<'\n';
}