Cod sursa(job #416439)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 12 martie 2010 19:37:17
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;


#define Nmax 1500

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

#define eps 0.0001

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

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]);
}

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


int cauta(double x, double y)
{
 int st=0, dr=N-1, m;
 
 while (st+1<dr)
       {
        m = (st+dr) >> 1;
        
        if (X[ind[m]]<x) dr=m;
           else st=m+1;
       }
 if (fabs(X[ind[st]]-x)<eps && fabs(Y[ind[st]]-y)<eps) return 1;
 if (fabs(X[ind[dr]]-x)<eps && fabs(Y[ind[dr]]-y)<eps) return 1;
 return 0;
}


void solve()
{
 int i, j;
 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()
{
 int i;
 
 freopen(file_out, "w", stdout);

 citire(); 
 
 for (i=0;i<N;++i)
     ind[i]=i;
 sort(ind,ind+N,cmp);

 solve();
 
 printf("%d\n",nr>>2);
 fclose(stdout);

 return 0;
}