Cod sursa(job #266070)

Utilizator vladbBogolin Vlad vladb Data 24 februarie 2009 21:23:41
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.21 kb
#include <stdio.h>  
  
#define Nmax 120200  
#define inf 10000000  
  
struct p{ double x,y; };  
  
p a[Nmax];  
  
int n,st[Nmax],vf=1;  
double minx=inf,miny=inf;  
  
int cmp(p A,p B,p C)  
{  
    double semn=((A.x-C.x)*(B.y-C.y)-(A.y-C.y)*(B.x-C.x));  
    if(semn>0) return 1;  
    if(semn<0) return -1;  
    return 0;  
}  
  
void qsort(int st,int dr)  
{  
    int i=st,j=dr;  
    p elem=a[(i+j)/2],aux;  
    do  
        {  
            while(cmp(a[1],a[i],elem) == 1) ++i;  
            while(cmp(a[1],elem,a[j]) == 1) --j;  
            if(i<=j)  
                {  
                    aux=a[i];  
                    a[i]=a[j];  
                    a[j]=aux;  
                    ++i;  
                    --j;  
                }  
        }while(i<=j);  
    if(st<j)   qsort(st,j);  
    if(i<dr)   qsort(i,dr);  
}  
  
  
int main()  
{  
    freopen("infasuratoare.in","r",stdin);  
    freopen("infasuratoare.out","w",stdout);  
  
    int i;  
  
    scanf("%d",&n);  
  
    for(i=1;i<=n;++i)  
        {  
            scanf("%lf%lf",&a[i].x,&a[i].y);  
            if(a[i].y<miny)  
                {  
                    miny=a[i].y;  
                    minx=a[i].x;  
                    a[0]=a[i];  
                    a[i]=a[1];  
                    a[1]=a[0];  
                }  
            else  
                if(a[i].y==miny)  
                    if(a[i].x<minx)  
                        {  
                            minx=a[i].x;  
                            a[0]=a[i];  
                            a[i]=a[1];  
                            a[1]=a[0];  
                        }  
        }  
  
/*  for(i=1;i<=n;++i) 
        printf("%lf %lf\n",a[i].x,a[i].y);  */  
    qsort(2,n);  
  
    st[vf]=1;  
  
    for(i=2;i<=n;++i)  
        {  
            while(vf>1 && cmp(a[st[vf-1]],a[st[vf]],a[i]) == -1)  
                --vf;  
            st[++vf]=i;  
        }  
/*  while(vf>1 && cmp(a[st[vf]],a[st[vf]],a[1]) == -1) 
        --vf; */  
  
    printf("%d\n",vf);  
    for(i=1;i<=vf;++i)  
        {  
            printf("%.6f %.6f\n",a[st[i]].x,a[st[i]].y);  
        }  
  
    return 0;  
}