Cod sursa(job #354341)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 7 octombrie 2009 19:11:20
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <stdio.h>
#define Nmax 1005
#define eps 0.0001

double x[Nmax],y[Nmax];
int n,i,j,patr;
double mijx,mijy,dx,dy;

double abs( double x ){
	return x>0 ? x : -x;
}

void sort(int l,int r){
	int i,j;
   double xx,yy,aux;
   i=l; j=r; xx=x[l+(r-l)/2]; yy=y[l+(r-l)/2];
   do{
   	while(x[i]<xx || ( abs(xx-x[i])<=eps && y[i]<yy)) i++;
      while(xx<x[j] || ( abs(x[j]-xx)<=eps && yy<y[j])) j--;
      if(i<=j){
      	aux=x[i]; x[i]=x[j]; x[j]=aux;
         aux=y[i]; y[i]=y[j]; y[j]=aux;
         i++; j--;
      }
   } while(i<=j);
   if(i<r) sort(i,r);
   if(l<j) sort(l,j);
}

int caut_bin(int l,int r,double xx, double yy){
	int m;//,nr=0;
  // if(xx) nr++;
   while(l<=r){
   	m=l+(r-l)/2;
      if( abs(x[m]-xx)<=eps && abs(y[m]-yy)<=eps) return 1;
      if( x[m]<xx || ( abs(xx-x[m])<=eps && y[m]<yy) ) l=m+1;
      else r=m-1;
   }
   return 0;
}

int main(){
	freopen("patrate3.in","r",stdin);
   freopen("patrate3.out","w",stdout);
   scanf("%d",&n);
   for(i=1;i<=n;++i) scanf("%lf%lf",&x[i],&y[i]);

   sort(1,n);
   for(i=1;i<n;++i)
     for(j=i+1;j<=n;++j){
     		mijx=double((x[i]+x[j])/2);
         mijy=double((y[i]+y[j])/2);
         dx=abs(mijx-x[i]);
         dy=abs(mijy-y[i]);
         if(y[i] <= y[j])
         	if( caut_bin(i+1,n,mijx+dy,mijy-dx ))
              if( caut_bin(i+1,n,mijx-dy,mijy+dx ))
              		patr++;
         if(y[j] < y[i])
         	if( caut_bin(i+1,n,mijx-dy,mijy-dx ))
            	if( caut_bin(i+1,n,mijx+dy,mijy+dx ))
               	patr++;
     }

	printf("%d\n",patr);
   fclose(stdin); fclose(stdout);
   return 0;
}