Cod sursa(job #62732)

Utilizator ZuziFilip Sanziana Zuzi Data 23 mai 2007 21:36:32
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.14 kb
#include <stdio.h>
#define eps 0.00001
#define NMAX 1001

int n, num;
typedef struct
{ float x,y; } POINT;

POINT p[NMAX];

void read()
{
	int i;
	float a,b;
	scanf("%d", &n);
	for (i = 1; i <= n; i++)
	       {scanf("%f %f", &a, &b);
		p[i].x=a;
		p[i].y=b;
	       }
}

float FABS(float x)
{
  if (x>0.0)
	 return x;
  else
	 return (-1)*x;
}

int egal (float a,float b)
{
	if (FABS(a-b)<eps)
		return 1;
	else
		return 0;
}

int partitie(int st,int dr)
{
	POINT aux, pivot;
	int i,j;
	i = st-1;
	j = dr+1;
	pivot = p[(st+dr)/2];
		while(1)
		{
			do {++i;} while( (p[i].x < pivot.x) || ( egal(p[i].x,pivot.x) && p[i].y < pivot.y  ) );
			do {--j;} while( (p[j].x > pivot.x) || ( egal(p[i].x,pivot.x ) && p[i].y > pivot.y ) );
				if (i<j)
				{
					aux=p[i];
					p[i]=p[j];
					p[j]=aux;
				}
				else
					return j;
		}
}

void sort(int st, int dr)
{
	int m;
	if (st < dr)
	{
		m = partitie(st,dr);
		sort(st,m);
		sort(m+1, dr);
	}
}

int caut (POINT a, int st, int dr)
{
	int m;
	if (st > dr)
		return 0;
	else
	{
		m = (st+dr)/2;
		if ( egal (p[m].x,a.x) && egal(p[m].y,a.y) )
			return 1;
		else
		  if (p[m].x < a.x || ( egal(p[m].x,a.x) && p[m].y < a.y) )
		   caut (a,m+1,dr);
		  else
		   caut (a,st,m-1);
	}

}

void rezolv()
{
	int i, j;
	POINT m, a, b;
	float x1, y1, x2, y2;
		 for (i = 1; i < n; i++)
			for (j = i+1; j <= n; j++)
			{
			   m.x = (p[i].x+p[j].x)/2;
			   m.y = (p[i].y+p[j].y)/2;
			   y1 = FABS (m.x - p[i].x);
			   x1 = FABS (m.y - p[i].y);
			   y2 = FABS (m.x - p[j].x);
			   x2 = FABS (m.y - p[j].y);

			   if (p[i].y <p[j].y)
			   {
				   a.x = m.x - x1;
				   a.y = m.y + y1;
				   b.x = m.x + x2;
				   b.y = m.y - y2;

			   }
			   else
			   {   a.x = m.x + x1;
				   a.y = m.y + y1;
				   b.x = m.x - x2;
				   b.y = m.y - y2;


			   }


			   if (  caut(a,1,n) && caut (b,1,n)  )
				num++;
			}
}


int main()
{
	freopen("patrate3.in", "r", stdin);
	freopen("patrate3.out", "w", stdout);
	read();
	sort(1,n);
	rezolv();
	printf("%d",num/2);
	return 0;
}