Cod sursa(job #216481)

Utilizator ilincaSorescu Ilinca ilinca Data 24 octombrie 2008 18:23:08
Problema Patrate 3 Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <stdio.h>
#include <vector>
#include <algorithm>

#define eps 0.000001
#define maxn 1005
#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;
	if (p1.x < p2.x)
		return 1;
	return 0;
}

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