Cod sursa(job #1538266)

Utilizator andreiudilaUdila Andrei andreiudila Data 28 noiembrie 2015 18:42:53
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n,i;
double inf, xmin,ymin;
struct punct{

double x, y, tg;

} v[120001];

punct st[120001];
bool cmp(punct x, punct y){

return x.tg<y.tg;

};

double det(punct a, punct b, punct c)
{
    double d=0;
    d=d+ a.x * b.y + a.y * c.x + b.x * c.y - c.x * b.y - c.y * a.x - b.x * a.y;

    return d;
}
int main()
{
    inf=2000000000;
    xmin=inf;
    ymin=inf;

    fin>>n;

    for(i=1;i<=n;i++)
        {
        fin>>v[i].x>>v[i].y;
        if(v[i].x<xmin) xmin=v[i].x, ymin=v[i].y;
        else if(v[i].x==xmin) ymin=min(ymin, v[i].y);
        }

    for(i=1;i<=n;i++)
    {
        if(v[i].x==xmin && v[i].y==ymin) v[i].tg=-inf;
        else if(v[i].x==xmin) v[i].tg=inf;
        else v[i].tg=(v[i].y-ymin)/(v[i].x-xmin);

    }

    sort(v+1,v+n+1, cmp);

    int stlev=0;
    st[1]=v[1];
    st[2]=v[2];
    stlev=2;

    for(i=3;i<=n;i++)
    {
        while(det(st[stlev-1],st[stlev],v[i])<0 )
            --stlev;

        ++stlev;
        st[stlev]=v[i];

    }

    fout<<stlev<<'\n';

    for(i=1;i<=stlev;i++)
        fout<<setprecision(12)<<fixed<<st[i].x<<" "<<st[i].y<<'\n';

     return 0;
}