Cod sursa(job #416445)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 12 martie 2010 19:47:30
Problema Patrate 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
using namespace std;

#include <cstdio>
#include <cmath>
#include <algorithm>

#define Nmax 2000

int N, Pmax, nr;
int X[Nmax], Y[Nmax];
int ind[Nmax];

void citire()
{
	float a,b;
 int i;
 
 freopen("patrate3.in","r",stdin);
 scanf("%d",&N);
 for (i=0; i<N; ++i)
    {
		scanf("%f %f", &a, &b);
		X[i]=a*10000;
		if (X[i]%10==9) X[i]++;
		Y[i]=b*10000;
		if (Y[i]%10==9) Y[i]++;
		//printf("%d %d\n", X[i],Y[i]);
 }
}

int cmp(const int &a, const int &b)
{
	return ( (X[a]<X[b]) || ((X[a]==X[b]) && (Y[a]<Y[b])) );
}

int find(int x, int y)
{
 int p = Pmax;
 int nr = -1;
 
 while (p)
	 {
		 if ( X[ind[nr+p]] < x || (X[ind[nr+p]] == x && Y[ind[nr+p]] < y) ) nr+=p;
		 p>>=1;
		 while (nr+p>=N) p>>=1;
	 }
 return (X[ind[nr+1]] == x && Y[ind[nr+1]] == y);
}

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 ( find(x3, y3) && find(x4, y4) ) ++nr;

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

int main()
{
 int i;
 
 freopen("patrate3.out", "w", stdout);

 citire(); 
 
 for (i=0; i<N; ++i)
     ind[i] = i;
 sort(ind, ind+N, cmp);
 
 for (Pmax=1; Pmax<N; Pmax<<=1);
 Pmax>>=1;
 solve();
 
 printf("%d\n",nr>>2);
 fclose(stdout);

 return 0;
}