Cod sursa(job #281229)

Utilizator igsifvevc avb igsi Data 13 martie 2009 22:13:44
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include<fstream.h>

#define xx 120001

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

int n,pj,st[xx];
double x[xx],y[xx];

int det(int i,int j,int k)//adevarata cand are loc o intoarcere spre dreapta
{
    double q;
    q=((x[i]*y[j]+x[j]*y[k]+y[i]*x[k])-(x[k]*y[j]+x[j]*y[i]+x[i]*y[k]));
    return (q<=0 ? 1 : 0); }

int poz(int li,int ls)
{
    int aux,i=0,j=-1;
    double auxx;
    while(li<ls)
    {
      if(((x[li]-x[0])*(y[ls]-y[0]))<((x[ls]-x[0])*(y[li]-y[0])))
      {
        auxx=x[li]; x[li]=x[ls]; x[ls]=auxx;
        auxx=y[li]; y[li]=y[ls]; y[ls]=auxx;
        aux=-i; i=-j; j=aux;
      }
      li+=i;
      ls+=j;
    }
    return li;
}

void qsort(int li,int ls)
{
     int k;
     if(li<ls)
     {
       k=poz(li,ls);
       qsort(li,k-1);
       qsort(k+1,ls);
     }
}

int main()
{
    int i,nr=0;
    fin>>n;
    fin>>x[1]>>y[1];
    pj=1;
    for(i=2;i<=n;i++)
    {
      fin>>x[i]>>y[i];
      if(x[pj]>x[i] || (x[pj]==x[i] && y[i]<y[pj]))
        pj=i;
    }
    
    x[0]=x[pj];
    y[0]=y[pj];
    for(i=pj;i<n;i++)
    { 
       x[i]=x[i+1];
       y[i]=y[i+1];
    }
    x[n]=y[n]=0;
    n--;
    qsort(1,n);
    
    st[++nr]=0;
    
    for(i=1;i<=n;i++)
    {
      while(nr>=2 && det(st[nr-1],st[nr],i)) --nr;
      st[++nr]=i;
    }
    
    fout<<nr<<'\n';
    for(i=1;i<=nr;i++)
     fout<<x[st[i]]<<' '<<y[st[i]]<<'\n';
    
    fout.close();
    return 0;
}