Cod sursa(job #17482)

Utilizator peanutzAndrei Homorodean peanutz Data 15 februarie 2007 23:38:03
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 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("%ld ", &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;
int st, dr, m;
long suma;

for(for1 = 0; for1 < n; ++for1)
		for(for2 = for1+1; for2 < n; ++for2)
			{
				st = for2+1;
				dr = n;
				suma = a[for1] + a[for2];

				while(st <= dr)
					{
						m = (st+dr)/2;

						if(a[m] > suma  &&  a[m-1] <= suma)
							{
								break;
							}
						else if(a[m] > suma)
							{
								st = m+1;
							}
						else
							{
								dr = m-1;
							}
					}
				if(m != st)
					count += m-st;
			}

}


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;
}