Cod sursa(job #128280)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 26 ianuarie 2008 19:34:23
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#include<stdio.h>
#include<math.h>
long int n,i,j,sol,ok,st,dr,mi;
double x[1001],y[1001],xx,yy,x2,y2,x3,y3,x4,y4,aux,eroare;
void swap(long int i1,long int i2);
long int comp(float a1,float b1,float a2,float b2);
void heapdown(long int ic,long int nc);
void cauta();
int main()
{
	FILE *f,*g;f=fopen("patrate3.in","r");g=fopen("patrate3.out","w");
	fscanf(f,"%ld",&n);
	eroare=0.0001;
	for(i=1;i<=n;i++)fscanf(f,"%lf%lf",&x[i],&y[i]);
	for(i=n/2;i>=1;i--) heapdown(i,n);
	for(i=n;i>=1;i--){swap(1,i);heapdown(1,i-1);}
	for(i=1;i<n;i++)
	 { xx=2*x[i];yy=2*y[i];
	    for(j=i+1;j<=n;j++)
		{ x2=2*x[j];y2=2*y[j];
		  x3=xx+x2+yy-y2;
		  y3=-xx+x2+yy+y2;
		  ok=0;st=i+1;dr=n;
		  cauta();
		  if(ok)
		  { x3=xx+x2-yy+y2;
		    y3=xx-x2+yy+y2;
		    ok=0;st=i+1;dr=n;
		    cauta();
		    if(ok)
		    sol++;
		  }
		}
	 }
	fprintf(g,"%ld\n",sol);
	fcloseall();
	return 0;
}
void swap(long int i1,long int i2)
{
	aux=x[i1];x[i1]=x[i2];x[i2]=aux;
	aux=y[i1];y[i1]=y[i2];y[i2]=aux;
}
long int comp(double a1,double b1,double a2,double b2)
{
	if(((a1>=a2)&&((a1-a2)<=eroare))||((a2>=a1)&&((a2-a1)<=eroare)))
	 if(((b1>=b2)&&((b1-b2)<=eroare))||((b2>=b1)&&((b2-b1)<=eroare)))
	  return 0;
	if(a1>a2) return 1;
	if(a1<a2) return -1;
	if(b1<b2) return -1;
	if(b1>b2) return 1;
	return 0;
}
void heapdown(long int ic,long int nc)
{
	long int is,is1;
	is=2*ic;is1=2*ic+1;
	if(is>nc) return;
	if(is<nc) if(comp(x[is],y[is],x[is1],y[is1])<0)is=is1;
	if(comp(x[is],y[is],x[ic],y[ic])>0){swap(ic,is);heapdown(is,nc);}
}
void cauta()
{
	if(st==dr)
	{ if(comp(x3,y3,2*x[dr],2*y[dr])==0) ok=1;return;}
	if(comp(x3,y3,2*x[st],2*y[st])<0) return;
	if(comp(x3,y3,2*x[dr],2*y[dr])>0) return;
	mi=(st+dr)/2;
	if(comp(x3,y3,2*x[mi],2*y[mi])<=0) {dr=mi;cauta();return;}
	st=mi+1;cauta();return;
}