Cod sursa(job #128279)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 26 ianuarie 2008 19:29:23
Problema Patrate 3 Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 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=x[i];yy=y[i];
	    for(j=i+1;j<=n;j++)
		{ x2=x[j];y2=y[j];
		  x3=(xx+x2+yy-y2)/2;
		  y3=(-xx+x2+yy+y2)/2;
		  ok=0;st=i+1;dr=n;
		  cauta();
		  if(ok)
		  { x3=(xx+x2-yy+y2)/2;
		    y3=(xx-x2+yy+y2)/2;
		    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,x[dr],y[dr])==0) ok=1;return;}
	if(comp(x3,y3,x[st],y[st])<0) return;
	if(comp(x3,y3,x[dr],y[dr])>0) return;
	mi=(st+dr)/2;
	if(comp(x3,y3,x[mi],y[mi])<=0) {dr=mi;cauta();return;}
	st=mi+1;cauta();return;
}