Cod sursa(job #217318)

Utilizator ilincaSorescu Ilinca ilinca Data 27 octombrie 2008 22:57:44
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.03 kb
#include <stdio.h>
#include <vector>
#include <algorithm>

#define eps 0.0001
#define maxn 10015
#define pr(x) fprintf(stderr, #x" = %d\n", x)
#define pf(x) fprintf(stderr, #x" = %lf\n",x)
#define x first
#define y second

using namespace std;

typedef pair <double, double> point;

int n, step;
point p [maxn];

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

inline double abs (double a)
{
	return a>=0? a:-a;
}

inline int egale (double x, double y)
{
	if (abs (x-y) < eps)
		return 1;
	return 0;
}

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

inline int conditie (point p1, point p2) 
{
	//0 - p1 se afla dupa p2
	//1 - p1 se afla inaintea lui p2 sau punctele coincid
	if (egale (p1.x, p2.x))
		if (egale (p1.y, p2.y) || p1.y < p2.y)
			return 1;
		else
			return 0;
	if (p1.x < p2.x)
		return 1;
	return 0;
}

/*inline int conditie1 (point p1, point p2) 
{
	//0 - p1 se afla dupa p2 punctele coincid
	//1 - p1 se afla inaintea lui p2 
	if (egale (p1.x, p2.x))
		if (egale (p1.y, p2.y) || p1.y > p2.y)
			return 0;
	if (p1.x > p2.x)
		return 0;
	return 1;
}*/


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

/*int cautbin (point T)
{
	int l, r, m;
	l=1;
	r=n;
	while (l < r)
	{
		m=(l+r)/2;
		if (conditie1 (p [m], T) == 0) 
			r=m;
		else
			l=m+1;
	}
	if (egale (T.x, p [r].x) && egale (T.y, p [r].y))
		return 1;
	return 0;
}*/

int patrate ()
{
	int i, j, nrp=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))
				++nrp;
		}
	return nrp>>1;
}

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