Cod sursa(job #132621)

Utilizator MarquiseMarquise Marquise Data 6 februarie 2008 11:30:21
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 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 s, int st, int dr)
{
	int m;

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

	return dr;

}


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++)
		{

			s = l[i] + l[j];
			c = caut(s, j+1, n);
			if ( s >= l[c] && c >= j + 1)
			{

				if ( s == l[c] )
				{
					for ( k = c; l[k] == s; k++);
						k--;
					num += k - j;
				}
			else
				num += c - j;
			}
		}
	printf("%d\n", num);
	return 0;
}