Cod sursa(job #286845)

Utilizator aaabbbaaa bbb aaabbb Data 24 martie 2009 11:24:34
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include<stdio.h>
FILE *f,*g;
float x[1000],y[1000],w[1000],aux,minx,miny,sup;
int i,n,v[1000],o,auxx,minxy,j,st[1000],k;
float sinn(int a,int 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(int v1,int v2,int 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=10000;miny=10000;
  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;
		 }
  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.000000000001)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--;
  for(i=1;i<=k;i++)fprintf(g,"%f %f\n",x[st[i]],y[st[i]]);
  return 0;
}