Cod sursa(job #132055)

Utilizator MarquiseMarquise Marquise Data 4 februarie 2008 22:29:09
Problema Patrate 3 Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.94 kb
#include <stdio.h>

#define NMAX 1001
#define eps 0.0000001

struct PUNCT
{
   double x, y;
};

PUNCT p[NMAX];

int n, num;

int partitie(int st, int dr)
{
	int i, j;
	PUNCT aux, pivot;
	i = st - 1;
	j = dr + 1;
	pivot = p[(st+dr)/2];
	while (1)
	{
		do {++i;} while ( p[i].x < pivot.x || ( p[i].x == pivot.x && p[i].y < pivot.y) );
		do {--j;} while ( p[j].x > pivot.x || ( p[j].x == pivot.x && p[j].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);
	}
}
inline double ABS(double x){return x < 0? -x: x;}


int egale(PUNCT a, PUNCT b)
{
	double x, y;
	x = ABS ( a.x-b.x);
	y = ABS ( a.y-b.y);
	if ( x < eps && y < eps)
		return 1;
	else
		return 0;
}


int exista(PUNCT p3)
{
	int st, dr, m;
	st = 1;
	dr = n;
	while ( st <= dr)
	{
		m = (st+dr) / 2;
		if ( egale(p[m],p3) )
			return 1;
		else
		{
			if ( p[m].x < p3.x || ( p[m].x == p3.x && p[m].y < p3.y) )
				st = m+1;
			else
				dr = m-1;

		}
	}

	return 0;
}




int main()
{
	int i, j;
	double mx, my, dx, dy, a, b;
	PUNCT p3, p4;
	freopen("patrate3.in", "r", stdin);
	freopen("patrate3.out", "w", stdout);

	scanf(" %d", &n);


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

	sort(1, n);

	for ( i = 1; i < n; i++)
		for ( j = i+1; j <= n; j++)
		{
			mx = (p[i].x + p[j].x) / 2;
			my = (p[i].y + p[j].y) / 2;
			dx = ABS(mx - p[i].x);
			dy = ABS(my - p[i].y);
			if ( p[i].y < p[j].y)
			{
				p3.x = mx + dy;
				p3.y = my - dx;
				p4.x = mx - dy;
				p4.y = my + dx;
			}
			else
			{
				p3.x = mx - dy;
				p3.y = my - dx;
				p4.x = mx + dy;
				p4.y = my + dx;
			}
			if ( exista(p3) && exista(p4) )
				num++;

		}
   printf("%d\n", num / 2);

	return 0;
}