Cod sursa(job #131026)

Utilizator MarquiseMarquise Marquise Data 2 februarie 2008 22:00:45
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <stdio.h>

#define NMAX 1001
#define NMAX2 500010                            


int n, nr;

struct PANTA
{
	long long y, x;
};

PANTA a[NMAX];
PANTA m[NMAX2];


int partitie(int st, int dr)
{
	int i, j;
	PANTA pivot, aux;
	pivot = m[(st+dr) / 2];
	i = st - 1;
	j = dr + 1;
	while (1)
	{
		do {++i;} while ( m[i].y * pivot.x < m[i].x * pivot.y);
		do {--j;} while ( m[j].y * pivot.x > m[j].x * pivot.y);
		if ( i < j)
		{
			aux = m[i];
			m[i] = m[j];
			m[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);
	}
}


int main()
{
	int i, j;
	long long rez = 0, l;
	freopen("trapez.in", "r", stdin);
	freopen("trapez.out", "w", stdout);
	scanf("%d", &n);
	for ( i = 1; i <= n; i++)
	{
		scanf("%d %d", &a[i].x, &a[i].y);
		for ( j = 1; j < i; j++)
		{
			m[++nr].x = a[i].x - a[j].x;
			m[nr].y = a[i].y - a[j].y;
			if ( m[nr].x < 0)
			{
				m[nr].x *= -1;
				m[nr].y *= -1;
			}
		}
	}
	sort(1, nr);
	m[nr+1].x = 1000;
	for ( i = 1; i <= nr; )
	{
		for ( j = i; m[j].y * m[j+1].x == m[j].x * m[j+1].y && j <= nr; j++);
		if ( i != j)
		{
			l = j - i + 1;
			rez += l*(l-1) / 2;
			i = j;
		}
		else
			i++;
	}
	printf("%lld", rez);

	return 0;
}