Cod sursa(job #215026)

Utilizator ilincaSorescu Ilinca ilinca Data 17 octombrie 2008 13:33:15
Problema Patrate 3 Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 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, step;
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);
	for (step=1; step<=n; step<<=1);
}

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


inline int conditie (int w, point A)
{
	if (w > n)
		return 0;
	if (A.x > p [w].x)
		return 1;
	if (egale (p [w].x, A.x) && (A.y > p [w].y || egale (A.y, p [w].y)))
		return 1;
	return 0;
}


int cautbin (point A)
{
	int s=step, i;
	for (i=0; s; s>>=1)
		if (conditie (i+s, A))
			i+=s;
	if (!egale (p [i].x, A.x))
		return 0;
	if (!egale (p [i].y, A.y))
		return 0;
	return 1;
}

long long patrate ()
{
	int i, j;
	long long 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 (c) && cautbin (d))
				++np;
		}
	return np/2;
}

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