Cod sursa(job #243914)

Utilizator drag0s93Mandu Dragos drag0s93 Data 14 ianuarie 2009 11:17:19
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include<stdio.h>
#include<stdlib.h>
const int N=30001;
int n,ap[N],sum[N],v[801],nr;
int n1=0;
void citire()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%d",&v[i]);
}
void calcul()
{
	int i,j,k,perechi=0;
	for(i=1;i<=n-2;++i)
	{
		k=i+2;
		for(j=i+1;j<=n-1;++j)
		{
			while(k<=n && v[i]+v[j]>=v[k])
				++k;
			perechi+=k-j-1;//k=indicele primului care nu e bun=>toate cele dintre j+1 si k-1 sunt bune
		}
	}
	printf("%d\n",perechi);
}

int compar(const void *p,const void *q)
{
	int x=*(int*)p,y=*(int*)q;
	if(x<y)
		return -1;
	if(x>y)
		return 1;
	return 0;
}

int main()
{
	freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);
	citire();
	qsort(v+1,n,sizeof(v[0]),compar);
	calcul();
	return 0;
}