Cod sursa(job #68313)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 27 iunie 2007 15:41:14
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include<stdio.h>
#include<fstream.h>
#include<math.h>

int n, contor;
typedef struct
{
  float x, y;
} punct;

punct a[1010];

void buble()
{
  int ok, i, j;
  punct aux;
  ok=0;
  while(!ok)
    {
      ok=1;
      for(i=1; i<n; i++)
	for (j=i+1; j<=n; j++)
	  {
	   if (a[i].x>a[j].x)
	     {
	       aux=a[i];
	       a[i]=a[j];
	       a[j]=aux;
	       ok=0;
	     }
	     else if (a[i].x==a[j].x && a[i].y>a[j].y)
		    {
		      aux=a[i];
		      a[i]=a[j];
		      a[j]=aux;
		      ok=0;
		    }
	  }

    }
}

int cautare(punct x, int p, int u)
{
  int m;
  m=(p+u)/2;
  do
  {
    if (p>u) break;
    if (a[m].x==x.x && a[m].y==x.y) return 1;
    else
     {
       if (a[m].x<=x.x) { p=m+1;m=(p+1)/2;}
	 else {u=m-1; m=(p+u)/2;}
     }
  }  while (p<u);
  return 0;
}


int main()
{
  freopen("patrate3.in","r",stdin);
  freopen("patrate3.out","w",stdout);

  scanf("%d",&n);
  int i, j;
  float mijx, mijy, dx, dy;
  punct x1, x2;
  for (i=1; i<=n; i++)
     {scanf("%f %f",&a[i].x,&a[i].y);
     }
  buble();

  for (i=1; i<=n-3; i++)
    for (j=i+1; j<=n-2; j++)
      {
	mijx=(a[i].x+a[j].x)/2;
	mijy=(a[i].y+a[j].y)/2;
	dx=abs(mijx-a[i].x);
	dy=abs(mijy-a[i].y);
	if (a[i].y<a[j].y)
	  {
	    x1.x=mijx+dy;
	    x1.y=mijy-dx;
	    x2.x=mijy-dy;
	    x2.y=mijy+dx;
	  }
	  else
	   {
	    x1.x=mijx+dy;
	    x1.y=mijy+dx;
	    x2.x=mijy-dy;
	    x2.y=mijy-dx;
	   }
	if (cautare(x1, j, n) && cautare(x2, j, n)) contor++;
      }
  printf("%d",contor);
  return 0;
}