Cod sursa(job #526307)

Utilizator andrei.dAndrei Diaconeasa andrei.d Data 27 ianuarie 2011 23:23:28
Problema Patrate 3 Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <cstdio>
#include <cmath>
#include <vector>

using namespace std;

#define file_in "patrate3.in"
#define file_out "patrate3.out"

#define Nmax 2123
#define Mod 666013
#define eps 0.00001

int N, nr,beg;
int X[Nmax], Y[Nmax];
vector<int> H[Mod];
char s[100];

int afla()
{
	int q=0;

	for (;s[beg] && '0'<=s[beg] && s[beg]<='9';++beg)
		q=q*10+s[beg]-'0';
    return q;
}

void citire()
{
 int i,x,x1,xx,yy,y,y1,e,e1;
 
 freopen(file_in,"r",stdin);
 scanf("%d",&N);
 for (i=0; i<N; ++i){
	   fgets(s, 100, stdin);
		beg = 0;
		e=e1=0;
		if (s[beg]=='-') 
			e=1,beg++;
		x=afla();
		beg++;
		x1=afla();
		for (;s[beg] && s[beg]==' ';++beg);
		if (s[beg]=='-') 
			e1=1,beg++;
		y=afla();
		beg++;
		y1=afla();
		if (!e) 
			xx=x*10000+x1;
		else 
			xx=(-x)*10000-x1;
		if (!e1) 
			yy=y*10000+y1;
		else 
			yy=(-y)*10000-y1;
		X[i]=xx;
		Y[i]=yy;
 }

}


inline int hash_it(int x,int y)
{
return ((int) (x+y))&(Mod-1);
}

void baga_hash()
{
 int i,key;
 
 for (i=0;i<N;++i)
     {
      key=hash_it(X[i], Y[i]);
      H[key].push_back(i);
     }
}

int cauta(int x,int y)
{
 vector<int> :: iterator it;
 int key=hash_it(x, y);
 for (it=H[key].begin();it<H[key].end();++it)
     if (x==X[*it]&& y==Y[*it]) 
		 return 1;
 return 0;
}

void solve()
{
 int i,j;
 int dx, dy, x3, x4, y3, y4;

 for (i=0;i<N;++i)
     for (j=i+1;j<N;++j)
         {
          dx=X[i]-X[j];
          dy=Y[i]-Y[j];

          x3=X[j]+dy;
          y3=Y[j]-dx;
          x4=X[i]+dy;
          y4=Y[i]-dx;
          if (cauta(x3,y3) && cauta(x4,y4)) 
			  ++nr;

          x3=X[j]-dy;
          y3=Y[j]+dx;
          x4=X[i]-dy;
          y4=Y[i]+dx;
          if (cauta(x3,y3) && cauta(x4,y4)) 
			  ++nr;
         }
}

int main()
{
 freopen(file_out, "w", stdout);

 citire(); 
 baga_hash();
 solve();
 
 printf("%d\n",nr/4);
 fclose(stdout);

 return 0;
}