Cod sursa(job #1484702)

Utilizator SagunistuStrimbu Alexandru Sagunistu Data 11 septembrie 2015 18:03:16
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <cstdio>
#include <algorithm>
#define eps 10e-12
#define punct pair<double,double>
#define nmax 120005
#define xx first
#define yy second

using namespace std;

int n,st[nmax],vf,viz[nmax];
punct p[nmax];

void citire()
{
    double a,b;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lf%lf",&a,&b);
        p[i]=make_pair(a,b);
    }
}

double sarrus(punct p1,punct p2,punct p3)
{
    return p1.xx*p2.yy+p2.xx*p3.yy+p3.xx*p1.yy-p1.yy*p2.xx-p2.yy*p3.xx-p3.yy*p1.xx;
}

void rezolv()
{
    st[++vf]=1;
    st[++vf]=2;
    viz[1]=1;
    viz[2]=1;
    for(int i=3;i<=n;i++)
    {
        while(viz[i]==0&&sarrus(p[st[vf-1]],p[st[vf]],p[i])<eps)
        {
            viz[st[vf]]=0;
            vf--;
            if(vf<2)
                break;
        }
        st[++vf]=i;
        viz[i]=1;
    }
    for(int i=n-1;i>=1;i--)
    {
        while(viz[i]==0&&sarrus(p[st[vf-1]],p[st[vf]],p[i])<=0)
        {
            viz[st[vf]]=0;
            vf--;
            if(vf<2)
                break;
        }
        if(viz[i]==0)
            st[++vf]=i,viz[i]=1;;
    }
}

void afisare()
{
    printf("%d\n",vf);
    for(int i=1;i<=vf;i++)
        printf("%lf %lf\n",p[st[i]]);
}

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    citire();
    sort(p+1,p+n+1);
    rezolv();
    afisare();
    return 0;
}