Cod sursa(job #416461)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 12 martie 2010 20:05:32
Problema Patrate 3 Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 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;
long double X[Nmax], Y[Nmax];
vector<int> H[Mod];

void citire()
{
 int i;
 
 freopen(file_in,"r",stdin);
 scanf("%d",&N);
 for (i=0; i<N; ++i)
      scanf("%Lf %Lf", &X[i], &Y[i]);
}


inline int hash_it(long double x,long double 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(long double x,long double y)
{
 vector<int> :: iterator it;
 int key=hash_it(x, y);
 for (it=H[key].begin();it<H[key].end();++it)
     if (fabs(x-X[*it])<eps && fabs(y-Y[*it])<eps) 
		 return 1;
 return 0;
}

void solve()
{
 int i,j;
 long double 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>>2);
 fclose(stdout);

 return 0;
}