Cod sursa(job #41075)

Utilizator peanutzAndrei Homorodean peanutz Data 27 martie 2007 22:26:34
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <stdio.h>

#define NMAX 1010
#define CMAX 1001*(1001-1)/2

typedef struct punct
{
long x, y;
};
int n;
punct p[NMAX];

punct c[CMAX];
long h;
long long count;

inline long abs(long a)
{
	if(a > 0)
		return a;
	return (-a);
}

void read()
{
	int i;
	scanf("%d\n", &n);

	for(i = 0; i < n; ++i)
		scanf("%ld %ld\n", &p[i].x, &p[i].y);
}

void fa_perechi()
{
	int i, j;

	for(i = 0; i < n; ++i)
		for(j = i+1; j < n; ++j)
		{
			c[h].x = abs(p[i].x - p[j].x);
			c[h++].y = abs(p[i].y - p[j].y);
		}
}

inline int conditie(punct a, punct b)
{
	if((a.x > b.x) || ((a.x == b.x) && (a.y > b.y)))
		return 0;
	return 1;
}

long divide(long p, long q)
{
	long st = p, dr = q;
	punct x = c[p];

	while(st < dr)
	{
		while((st < dr) && !conditie(c[dr], x)) --dr;
		c[st] = c[dr];

		while((st < dr) && conditie(c[st], x)) ++st;
		c[dr] = c[st];
	}

	c[st] = x;
	return st;
}

void qsort(long p, long q)
{
	long m = divide(p, q);

	if(m > p)
		qsort(p, m-1);
	if(m < q)
		qsort(m+1, q);
}

void solve()
{
	long i;
	punct aux;
	int nr = 1;

	aux.x = c[0].x;
	aux.y = c[0].y;

	for(i = 1; i < h; ++i)
	{
		if(aux.x == c[i].x && aux.y == c[i].y)
		{
			++nr;
		}
		else
		{
			if(nr > 1)
				count += (nr*(nr-1)/2);

			nr = 1;
			aux.x = c[i].x;
			aux.y = c[i].y;
		}
	}
}

int main()
{
	freopen("trapez.in", "r", stdin);
	freopen("trapez.out", "w", stdout);

	read();

	fa_perechi();

	qsort(0, h-1);

	solve();

	printf("%lld\n", count);

	fclose(stdin);
	fclose(stdout);

	return 0;
}