Cod sursa(job #1238097)

Utilizator heracleRadu Muntean heracle Data 5 octombrie 2014 17:12:37
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.42 kb
#include <cstdio>



FILE* in=fopen("infasuratoare.in","r");
FILE* out=fopen("infasuratoare.out","w");

const int Q=100001;

struct point{
    double x,y;
} v[Q];

int n;

int inline clock(const point &a,const point &b,const point &c)
{
    double aux;

    aux=(double)(b.x-a.x)*(c.y-a.y)-(double)(c.x-a.x)*(b.y-a.y);

    if(aux>0)
        return 1;
    if(aux<0)
        return -1;

    return 0;
}

int ord[Q];

int stv[Q];

int ymin=1;

void select()
{
    stv[++stv[0]]=1;
    stv[++stv[0]]=ord[2];

    for(int i=3; i<=n; i++)
    {
        while(stv[0]!=0 && clock(v[stv[stv[0]-1]],v[stv[stv[0]]],v[ord[i]])==-1)
        {
            stv[0]--;
        }

        if(clock(v[stv[stv[0]-1]],v[stv[stv[0]]],v[ord[i]])==0)
        {
            if(v[stv[stv[0]]].x<v[ord[i]].x)
            {
                stv[stv[0]]=ord[i];
            }
        }
        else
            stv[++stv[0]]=ord[i];

        if(v[stv[stv[0]-1]].y<v[stv[ymin]].y)
            ymin=stv[0]-1;
    }
    if(v[stv[stv[0]]].y<v[stv[ymin]].y)
        ymin=stv[0];
}

void q_sort(int st, int dr)
{
    int st0=st,dr0=dr;
    if(st>=dr)
        return;

    int p=st++,aux;

    while(st<=dr)
    {
        if(p<st)
        {
            if(clock(v[1],v[ord[st] ], v[ord[p] ] )==1)
            {
                aux=ord[p];
                ord[p]=ord[st];
                ord[st]=aux;
            }
            st++;
        }
        else
        {
            if(clock(v[1],v[ord[p]],v[ord[dr]])==1)
            {
                aux=ord[p];
                ord[p]=ord[dr];
                ord[dr]=aux;
            }
            dr--;
        }
    }
    q_sort(st0,p-1);
    q_sort(p+1,dr0);

}

void sort()
{
    for(int i=2; i<=n; i++)
    {
        ord[i]=i;
    }
    q_sort(2,n);
}

void read()
{

    int min=1;

    for(int i=1; i<=n; i++)
    {
        fscanf(in,"%lf %lf",&v[i].x,&v[i].y);

        if(v[i].x==v[min].x && v[i].y<v[min].y)
            min=i;
        if(v[i].x<v[min].x)
            min=i;
    }

    double aux;

    aux=v[1].x;
    v[1].x=v[min].x;
    v[min].x=aux;

    aux=v[1].y;
    v[1].y=v[min].y;
    v[min].y=aux;
}



int main()
{
    fscanf(in,"%d",&n);
    read();
    sort();
    select();

    fprintf(out,"%d\n",stv[0]);

    for(int i=ymin; i<=stv[0]; i++)
    {
        fprintf(out,"%.6lf %.6lf\n",v[stv[i]].x,v[stv[i]].y);
    }

    for(int i=1; i<ymin; i++)
    {
        fprintf(out,"%.6lf %.6lf\n",v[stv[i]].x,v[stv[i]].y);
    }

    return 0;
}