Cod sursa(job #52402)

Utilizator vmaneavmanea vmanea Data 18 aprilie 2007 20:17:23
Problema Numarare triunghiuri Scor 70
Compilator c Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <stdio.h>
#include <stdlib.h>
#define nmax 805

int *p1, *p2, N, i, j, k, tri;

int dif[nmax][nmax];

int L[nmax];

int sortit( const void *a, const void *b)
{
   p1 = (int *)a;

   p2 = (int *)b;

   if (*p1 < *p2)
	return -1;
   if (*p1 == *p2)
	return 0;
   return 1;
}


int main(void)
{
	freopen("nrtri.in", "r", stdin);
	freopen("nrtri.out", "w", stdout);

	scanf("%d", &N);

	for (i = 1; i <= N; ++i)
		scanf("%d", &L[i]);

	qsort((void *)L, N + 1, sizeof(int), sortit);

	for (i = 1; i <= N; ++i)
		for (j = i + 1; j <= N; ++j)
			dif[j][i] = dif[i][j] = L[i] - L[j] > 0? L[i] - L[j]: L[j] - L[i];

	for (i = 1; i <= N; ++i)
		for (j = i + 1; j <= N; ++j)
			for (k = j + 1; k <= N; ++k)
				if (L[i] + L[j] >= L[k])
				{
					if (L[i] >= dif[j][k] && L[j] >= dif[i][k] && L[k] >= dif[i][j])
						tri++;
				}
				else
					k = N;
	printf("%d\n", tri);

	return 0;
}