Cod sursa(job #58542)

Utilizator petrecgClinciu Glisca Petre petrecg Data 6 mai 2007 12:29:41
Problema Patrate 3 Scor 75
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <stdio.h>
long double x[2001],y[2001],x0,y0,x1,y1,mijx,mijy,dx,dy,z;
long p,l,q,n,i,j,z1,z2,zz,nr,ll,l1,l2,v[2001];
int cauta(long double xx,long double yy,long p,long q)
{l=(p+q)/2;
 if(x[l]-xx<0.0001&&x[l]-xx>-0.0001&&y[l]-yy<0.0001&&y[l]-yy>-0.0001){ll=l;zz=1;}
 else
 if(p!=q)
 {
 if(x[l]>=xx+0.0001)cauta(xx,yy,p,l);else if(x[l]<=xx-0.0001)cauta(xx,yy,l+1,q);
 else if(y[l]>=yy+0.0001)cauta(xx,yy,p,l);else cauta(xx,yy,l+1,q);
 }
 return 0;
}
int main()
{freopen("patrate3.in","r",stdin);
 freopen("patrate3.out","w",stdout);
 fscanf(stdin,"%ld",&n);
 for(i=1;i<=n;i++)fscanf(stdin,"%Lf%Lf",&x[i],&y[i]);
 for(i=1;i<n;i++)for(j=i+1;j<=n;j++)
  {if(x[i]>x[j]){z=x[i];x[i]=x[j];x[j]=z;z=y[i];y[i]=y[j];y[j]=z;}
   if(x[i]==x[j]&&y[i]>y[j]){z=y[i];y[i]=y[j];y[j]=z;}
  }
 fclose(stdin);
 for(i=1;i<n;i++)for(j=i+1;j<=n;j++)
 {if(v[i]+v[j]<2)
  {mijx=(x[i]+x[j])/2;mijy=(y[i]+y[j])/2;
  dx=mijx-x[i];dy=mijy-y[i];if(dx<0)dx=-dx;if(dy<0)dy=-dy;
  if(y[i]<y[j]){x0=mijx+dy;y0=mijy-dx;x1=mijx-dy;y1=mijy+dx;}
	   else{x0=mijx-dy;y0=mijy-dx;x1=mijx+dy;y1=mijy+dx;}
  zz=0;cauta(x0,y0,1,n);z1=zz;l1=ll;zz=0;cauta(x1,y1,1,n);z2=zz;l2=ll;
  if(z1+z2==2){v[l1]=1;v[l2]=1;nr++;}}
 }
 fprintf(stdout,"%ld",nr);fclose(stdout);
 return 0;
}