Cod sursa(job #17465)

Utilizator peanutzAndrei Homorodean peanutz Data 15 februarie 2007 22:38:16
Problema Numarare triunghiuri Scor 75
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <stdio.h>

#define NMAX 1000

int n;
long a[NMAX];
long long count;

void read()
{
int i;

scanf("%d\n", &n);

for(i = 0; i < n; ++i)
	scanf("%d ", &a[i]);
}

int divide(int p, int q)
{
int st = p, dr = q;
long x = a[p];

while(st < dr)
	{
		while(st < dr  &&  x <= a[dr]) --dr;
		a[st] = a[dr];

		while(st < dr  &&  x >= a[st]) ++st;
		a[dr] = a[st];
	}
a[st] = x;

return st;
}

void qsort(int p, int q)
{
int m = divide(p, q);

if(m-1 > p)
	qsort(p, m-1);
if(m+1 < q)
	qsort(m+1, q);

}

void solve()
{
int for1, for2, for3;

for(for1 = 0; for1 < n; ++for1)
		for(for2 = for1+1; for2 < n; ++for2)
			for(for3 = for2+1; for3 < n; ++for3)
				{
					if((a[for1] + a[for2] >= a[for3])  &&  (a[for1] + a[for3] >= a[for2])  &&  (a[for2] + a[for3] >= a[for1]))
						++count;
					else
						break;
				}
}


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

read();

qsort(0, n-1);

solve();

printf("%lld\n", count);

fclose(stdin);
fclose(stdout);

return 0;
}