Cod sursa(job #2358089)

Utilizator HoratioHoratiu Duma Horatio Data 27 februarie 2019 21:20:58
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;


const double epsil=1e-12;


struct punct
{
    double x,y;

} M[125000];

bool viz[125000];

int Q[125000];


bool operator<(punct& a,punct& b)
{
    if(a.x!=b.x)
        return a.x<b.x;
    else
        return a.y<b.y;
}


double col(punct A, punct B, punct C)
{
    return (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);
}

int main()
{

    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    int n;
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        double a,b;
        scanf("%lf %lf",&a,&b);
        M[i].x=a;
        M[i].y=b;
    }

    sort(M+1,M+n+1);

    int l=2;

    Q[1]=1;
    Q[2]=2;

    viz[2]=1;

    for(int i=1; i<=n; i++)
    {
        if(viz[i])
            continue;
        else
        {
            while(l>=2 && col(M[Q[l-1]],M[Q[l]],M[i])<epsil)
                viz[Q[l--]]=0;
            Q[++l]=i;
            viz[i]=1;
        }
    }

    for(int i=n-1; i>=1; i--)
    {
        if(viz[i])
            continue;
        else
        {
            while(l>=2 && col(M[Q[l-1]],M[Q[l]],M[i])<epsil)
                viz[Q[l--]]=0;
            Q[++l]=i;
            viz[i]=1;
        }
    }
    printf("%d\n",l-1);
    for(int i=2;i<l;i++)
    {
        printf("%f %f\n",M[Q[i]].x,M[Q[i]].y);
    }
        printf("%f %f\n",M[Q[1]].x,M[Q[1]].y);


}