Cod sursa(job #413387)

Utilizator blasterzMircea Dima blasterz Data 8 martie 2010 14:27:10
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <cstdio>
#include <algorithm>

using namespace std;
int a[801];
int n;

void brut ()
{
	int i, j, k;
	int nr = 0;

	for (i = 1; i <= n-2; ++i)
		for (j = i + 1; j <= n-1; ++j)
			for (k = j + 1; k <= n; ++k)
				if (a[i] + a[j] >= a[k])
					++nr;

	printf ("%d\n", nr);
}

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

//	brut ();
	k = 0;
	int rez = 0;

	for (i = 1; i <= n-2; ++i)
		for (j = i + 1; j <= n-1; ++j)
		{
			for (k = max (k-4, j+1); k <= n && (a[i] + a[j] >= a[k]); ++k);
			
			
			if (a[i] + a[j] < a[j+1]) ;
			else rez += k - j - 1;
		}

	printf ("%d\n", rez);

//	brut ();
	return 0;
}