Cod sursa(job #132608)

Utilizator MarquiseMarquise Marquise Data 6 februarie 2008 11:05:46
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <stdio.h>

#define NMAX 801

int l[NMAX], n, num;


int partitie(int st, int dr)
{
	int i, j, aux, pivot;
	i = st - 1;
	j = dr +1;
	pivot = l[(st+dr)/2];
	while (1)
	{
		do {++i;} while ( l[i] > pivot);
		do {--j;} while ( l[j] < pivot);
		if ( i < j)
		{
			aux = l[i];
			l[i] = l[j];
			l[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 caut(int a, int b, int st, int dr)
{
	int m;

	while ( st <= dr)
	{
		m = (st+dr)/2;
		if ( l[m] + b == a )
			return m;
		else
			if ( l[m] + b > a)
				st = m + 1;
			else
				dr = m - 1;
	}

	return st > n ? n : st;

}


int main()
{
	int i, j, k, s, c;
	freopen("nrtri.in", "r", stdin);
	freopen("nrtri.out", "w", stdout);
	scanf("%d", &n);
	for ( i = 1; i <= n; i++)
		scanf("%d", &l[i]);
	sort(1,n);
	for ( i = 1; i < n; i++)
		for ( j = i+1; j < n; j++)
		{

			c = caut(l[i], l[j], j+1, n);
			if ( l[j] + l[c] >= l[i])
			{
			if ( l[i] + l[c] < l[j] )
			{
				for ( k = c; l[i] + l[k] < l[j] && k > j; k--)
				k++;
				num += k -j;
			}
			else
			if ( l[c] + l[j]== l[i] )
			{
				for ( k = c; l[k] +l[j] == l[i]; k++);
				k--;
				num += k - j;
			}
			else
				num += c - j;
			}
		}
	printf("%d\n", num);
	return 0;
}