Cod sursa(job #257694)

Utilizator igsifvevc avb igsi Data 13 februarie 2009 20:22:16
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include<stdio.h>

#define xx 120001

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

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;
    fscanf(fin,"%d",&n);
    fscanf(fin,"%lf %lf",&x[1],&y[1]);
    pi=1;
    for(i=2;i<=n;i++)
    {
        fscanf(fin,"%lf %lf",&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];
    }
    
    fprintf(fout,"%d\n",st[0]);
    for(i=st[0];i>0;i--)
      fprintf(fout,"%lf %lf\n",x[st[i]],y[st[i]]);
    
    fclose(fout);
    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;
}