Cod sursa(job #128283)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 26 ianuarie 2008 19:47:49
Problema Patrate 3 Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 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.00001;
	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++)
	 { for(j=i+1;j<=n;j++)
	    { x3=(x[i]+x[j]+y[i]-y[j])/2.0;
	      y3=(-x[i]+x[j]+y[i]+y[j])/2.0;
	      ok=0;st=i+1;dr=n;
	      cauta();
	      if(ok)
	      { x3=(x[i]+x[j]-y[i]+y[j])/2.0;
		y3=(x[i]-x[j]+y[i]+y[j])/2.0;
		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(fabs(a1-a2)<eroare&&fabs(b1-b2)<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;
}