Cod sursa(job #178666)

Utilizator nusmaibunkeleviprofesor cicalescu nusmaibunkelevi Data 14 aprilie 2008 21:44:29
Problema Numarare triunghiuri Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include<stdio.h>
#include<stdlib.h>

void poz(int stga,int drpta,int &pivot,int x[])
{
int i=stga,j=drpta,d=0,t;
while(i<j){
	if(x[i]>x[j]){t=x[i];x[i]=x[j];x[j]=t;d=1-d;}
	i+=d;
	j-=1-d;
	}
pivot=i;
}

void qsort(int x[],int st,int dr)
{
int p;
if(st<dr){
	poz(st,dr,p,x);
	qsort(x,st,p-1);
	qsort(x,p+1,dr);
	}
}

int main()
{
int n,v[800]={0},i,j,k,nrtri=0;
freopen("nrtri.in","r",stdin);
freopen("nrtri.out","w",stdout);
scanf("%d",&n);
for(i=0;i<n;i++)
	scanf("%d",&v[i]);

qsort(v,0,n-1);
for(i=0;i<n-2;i++)
	for(j=i+1;j<n-1;j++){
		if(v[i]+v[j]<v[j+1]) continue;
		for(k=j+1;k<n;k++){
			   //	if(v[i]+v[k]<v[j]) continue;
			if(v[i]+v[j]<v[k]) break;
			nrtri++;
			}
		}
printf("%d",nrtri);
return 0;
}