Cod sursa(job #128249)

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