Cod sursa(job #744214)

Utilizator iarbaCrestez Paul iarba Data 8 mai 2012 07:22:01
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <cstdio>
using namespace std;
int a[850],i,j,n,k;
long t;
void sortare(int x,int y)
{
	int piv=(x+y)/2,x0=x,y0=y,aux;
	while(x0<y0){
		    while(a[x0]<=a[piv]){x0++;}
			while(a[y0]>=a[piv]){y0--;}
			if(x0<y0){aux=a[x0];a[x0]=a[y0];a[y0]=aux;}
	            }
	if(y>x){
	sortare(x,piv);sortare(piv+1,y);
	       }
}
int main()
{
	freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++){scanf("%d",&a[i]);}
	sortare(1,n);
	for(i=n;i>=3;i--){
		for(j=i-1;j>=2;j--){
			for(k=j-1;k>=1;k--){
				if(a[k]<a[i]-a[j]){continue;}
				t++;
			                   }
		                   }
	                 }
	printf("%ld",t);
return 0;
}