Cod sursa(job #216339)

Utilizator ilincaSorescu Ilinca ilinca Data 23 octombrie 2008 22:39:17
Problema Patrate 3 Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 kb
#include <stdio.h>

#define nmax 1005
#define eps 0.0001
#define pr(x) fprintf(stderr,#x" = %d\n",x)
#define pf(x) fprintf(stderr,#x" = %lf\n",x)

struct point
{
	double x, y;
};

int n;
point p [nmax];



inline double abs (double x)
{
	if (x >= 0)
		return x;
	return -x;
}

void scan ()
{
	int i;
	scanf ("%d", &n);
	for (i=1; i<=n; ++i)
		scanf ("%lf%lf", &p [i].x, &p [i].y);
}

inline int egale (double a, double b)
{
	double dif;
	dif=abs (a-b);
	return (dif < eps);
}

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

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

void puncte (point A, point B, point &C, point &D)
{
	point M, d;
	M.x=(A.x+B.x)/2;
	M.y=(A.y+B.y)/2;
	d.x=abs (M.x-A.x);
	d.y=abs (M.y-A.y);
	if (A.y < B.y)
	{
		C.x=M.x+d.y;
		C.y=M.y-d.x;
		D.x=M.x-d.y;
		D.y=M.y+d.x;
	}
	else
	{
		C.x=M.x-d.y;
		C.y=M.y-d.x;
		D.x=M.x+d.y;
		D.y=M.y+d.x;
	}
}

int cautbin (int st, int dr, point A)
{
	int m;
	if (st > dr)
		return 0;
	m=(st+dr)/2;
	if (egale (A.x, p [m].x) && egale (A.y, p [m].y))
		return 1;
	if ((A.x < p [m].x) || (egale (A.x, p [m].x) && A.y < p [m].y))
		return cautbin (st, m-1, A);
	else
		return cautbin (m+1, dr, A);
}

int patrate ()
{
	int i, j, np=0;
	point c, d;
	for (i=1; i<=n; ++i)
		for (j=i+1; j<=n; ++j)
		{
			puncte (p [i], p [j], c, d);	
			if (cautbin (1, n, c) && cautbin (1, n, d))
				++np;
		}
	return np/2;
}

int main ()
{
	freopen ("patrate3.in", "r", stdin);
	freopen ("patrate3.out", "w", stdout);
	scan ();
	quicks (1, n);
	printf ("%d\n", patrate ());
	return 0;
}