Cod sursa(job #410288)

Utilizator ZillaMathe Bogdan Zilla Data 4 martie 2010 11:23:28
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.81 kb
#include <stdio.h>

#define Nmax 120100

struct punct{
    double x,y;
};

punct p[Nmax];

int n,vf,st[Nmax];
double minx,miny;

int cmp(punct i,punct j,punct k)
{
    double x=(j.x-i.x)*(k.y-i.y) - (k.x-i.x)*(j.y-i.y);
    if(x>0)  return 1;
    if(x<0)  return -1;
    return 0;
}

void qsort(int st,int dr)
{
    int i=st,j=dr;
    punct elem=p[(i+j)/2],tmp;
    do
        {
            while(cmp(p[1],p[i],elem)==1) ++i;
            while(cmp(p[1],elem,p[j])==1) --j;
            if(i<=j)
                {
                    tmp=p[i];
                    p[i]=p[j];
                    p[j]=tmp;
                    ++i;
                    --j;
                }
        }while(i<=j);

    if(i<dr)    qsort(i,dr);
    if(j>st)    qsort(st,j);

}

int main()
{
    int i;

    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d",&n);

    for(i=1;i<=n;++i)
        {
            scanf("%lf%lf",&p[i].x,&p[i].y);
            if(p[i].x<minx)
                {
                    punct elem=p[i];
                    p[i]=p[1];
                    p[1]=elem;
                    minx=p[1].x;
                    miny=p[1].y;
                }
            else
                if(p[i].x==minx && p[i].y<miny)
                    {
                        punct elem=p[i];
                        p[i]=p[1];
                        p[1]=elem;
                        miny=p[i].y;
                    }
        }

    qsort(2,n);

    st[++vf]=1;
    for(i=2;i<=n;++i)
        {
            while(vf>1 && cmp(p[st[vf-1]],p[st[vf]],p[i])==-1)
                --vf;
            st[++vf]=i;
        }
    printf("%d\n",vf);

    for(i=1;i<=vf;++i)
        printf("%lf %lf\n",p[st[i]].x,p[st[i]].y);

    return 0;
}