Cod sursa(job #286880)

Utilizator aaabbbaaa bbb aaabbb Data 24 martie 2009 11:51:01
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include<stdio.h>
FILE *f,*g;
float x[1200],y[1200],w[1200],aux,minx,miny,sup;
long i,n,v[1200],o,auxx,minxy,j,st[1200],k;
float sinn(long a,long b)
{if(x[b]>x[a])return (y[b]-y[a])*(y[b]-y[a])/((y[b]-y[a])*(y[b]-y[a])+(x[b]-x[a])*(x[b]-x[a]));
     else return 2-(y[b]-y[a])*(y[b]-y[a])/((y[b]-y[a])*(y[b]-y[a])+(x[b]-x[a])*(x[b]-x[a]));
}

float arie(long v1,long v2,long v3)
{return x[v1]*y[v2]-x[v2]*y[v1]+x[v2]*y[v3]-x[v3]*y[v2]+x[v3]*y[v1]-x[v1]*y[v3];
}

float modul(float x)
{if(x>0)return x;else return -x;
}
int main()
{ f=fopen("infasuratoare.in","r");
  g=fopen("infasuratoare.out","w");
  fscanf(f,"%ld",&n);minx=1000000000;miny=1000000000;
  for(i=1;i<=n;i++)
   { fscanf(f,"%f%f",&x[i],&y[i]);
     if(x[i]<minx)minx=x[i];
     if(y[i]<miny){miny=y[i];if(x[i]<x[minxy]||minxy==0)minxy=i;}
     v[i]=i;
   }
  if(minx<0)for(i=1;i<=n;i++)x[i]-=minx;
  if(miny<0)for(i=1;i<=n;i++)y[i]-=miny;
  o=minxy;
  for(i=1;i<=n;i++)if(i!=o)w[i]=sinn(o,i);
  for(i=1;i<n;i++)
   for(j=i+1;j<=n;j++)
    if(w[i]>w[j]){aux=w[i];w[i]=w[j];w[j]=aux;
		  auxx=v[i];v[i]=v[j];v[j]=auxx;
		 }
		 else if((w[i]==w[j]&&x[i]>x[j])||(w[i]==w[j]&&y[i]>y[j]))
		       {aux=w[i];w[i]=w[j];w[j]=aux;
			auxx=v[i];v[i]=v[j];v[j]=auxx;
		       }
  st[1]=o;st[2]=v[2];k=2;
  for(i=3;i<=n;i++)
   {sup=arie(st[k-1],st[k],v[i]);
    if(modul(sup)<=0.00000010001)st[k]=v[i];
      else  {while(arie(st[k-1],st[k],v[i])<0&&k>=2)k--;
		     k++;st[k]=v[i];
	     }
    }
  while(arie(st[k-1],st[k],1)<0)k--;
  fprintf(g,"%ld\n",k);
  for(i=1;i<=k;i++)fprintf(g,"%f %f\n",x[st[i]],y[st[i]]);
  return 0;
}