Cod sursa(job #41457)

Utilizator peanutzAndrei Homorodean peanutz Data 28 martie 2007 11:56:44
Problema Reuniune Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <stdio.h>
#include <math.h>

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

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

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

inline long double abs(long double 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;
        long double nextx, nexty;

	for(i = 0; i < n; ++i)
		for(j = i+1; j < n; ++j)
		{
			nextx = (p[i].x - p[j].x);
			nexty = (p[i].y - p[j].y);

			if(nexty == 0)
			{
				++count;
			}
			else
			{
				nextx = (long double)nextx/nexty;

				c[h++] = nextx;
				//floor(nextx*1000 000 000 000)/1000000000000;
			}

		}
	count = count * (count-1) / 2;
}


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

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

		while((st < dr) && 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;
	long double aux;
	int nr = 1;

	aux = c[0];

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

			nr = 1;
			aux = c[i];
		}
	}
}

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