Cod sursa(job #257618)

Utilizator igsifvevc avb igsi Data 13 februarie 2009 18:04:45
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include<fstream.h>

#define xx 120001

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

double x[xx],y[xx];
int ind[xx],st[xx],n,pi;

inline int semn(int i,int j,int k)// adevarata cand are loc o intoarcere spre dreapta
{
       return (((x[i]*y[j]+x[j]*y[k]+y[i]*x[k])-(x[k]*y[j]+x[j]*y[i]+x[i]*y[k]))>0 ? 1 : 0);
}

void quick(int,int);
int poz(int,int);

int main()
{
    int i;
    fin>>n;
    fin>>x[1]>>y[1];
    pi=1;
    for(i=2;i<=n;i++)
    {
        fin>>x[i]>>y[i];
        if(x[i]<x[pi] || (x[i]==x[pi] && y[i]<y[pi]))
              pi=i;
    }
    
    for(i=1;i<=n;i++)
      if(i!=pi)
        ind[++ind[0]]=i;
    
    quick(1,ind[0]);
    
    st[++st[0]]=pi;
    
    for(i=1;i<=ind[0];i++)
    {
       while(st[0]>=2 && semn(st[st[0]-1],st[st[0]],ind[i]))  --st[0];
       st[++st[0]]=ind[i];
    }
    
    fout<<st[0]<<'\n';
    for(i=st[0];i>0;i--)
      fout<<x[st[i]]<<' '<<y[st[i]]<<'\n';
    
    fout.close();
    return 0;
}

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

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