Cod sursa(job #128753)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 27 ianuarie 2008 19:48:05
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
long int n,i,j,sol,ok,st,dr,mi,s,x[1001],y[1001],xx,yy,x2,y2,x3,y3,x4,y4,aux,eroare;
char cit[20],*p,*q;
void swap(long int i1,long int i2);
long int comp(long int a1,long int b1,long int a2,long int 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);
	for(i=1;i<=n;i++)
	{ fscanf(f,"%s",cit);
	  p=cit;s=2;
	  if(*p=='-'){p++;s=-s;};
	  q=strchr(p,'.');q++;
	  x[i]=10000*atol(p)+atol(q);
	  x[i]*=s;
	  fscanf(f,"%s",cit);
	  p=cit;s=2;
	  if(*p=='-'){p++;s=-s;};
	  q=strchr(p,'.');q++;
	  y[i]=10000*atol(p)+atol(q);
	  y[i]*=s;
	}
	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])<<1;
	      y3=(-x[i]+x[j]+y[i]+y[j])<<1;
	      ok=0;st=i+1;dr=n;
	      cauta();
	      if(ok)
	      { x3=(x[i]+x[j]-y[i]+y[j])<<2;
		y3=(x[i]-x[j]+y[i]+y[j])<<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(long int a1,long int b1,long int a2,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 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;
}