Cod sursa(job #744217)

Utilizator iarbaCrestez Paul iarba Data 8 mai 2012 07:37:52
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <cstdio>
using namespace std;
int a[850],i,j,n,k;
long t;
void sortare(int x,int y)
{
	int x0,y0,piv,aux;
	x0=x;y0=y;piv=a[(x+y)/2];
	do{
		while(a[x0]<piv){x0++;}
		while(a[y0]>piv){y0--;}
		if(x0<=y0){
			aux=a[x0];a[x0]=a[y0];a[y0]=aux;;
			x0++;y0--; 
          }
	}while(i<=j);
	if(x<y0){sortare(x,y0);}
	if(x0<y){sortare(x0,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]){t--;k=0;}
				t++;
			                   }
		                   }
	                 }
	printf("%ld",t);
return 0;
}