Cod sursa(job #203998)

Utilizator AthanaricCirith Gorgor Athanaric Data 21 august 2008 13:27:04
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <stdio.h>
#include <stdlib.h>
int n,v[850];
int compar(const void*p, const void*q)
{
	int *pp=(int*)p, *qq=(int*)q;
	if (*pp<*qq)
		return -1;
	if (*pp>*qq)
		return 1;
	if (*pp==*qq)
		return 0;
}
int caut(int x,int s, int d)
{
	int m;
	while (s<d)
	{
		m=(s+d)/2;
		if (v[m]>=x)
			s=m+1;
		else 
			d=m;
	}
	if (v[s]>x)
		return s;
	return n;
}

int main()
{
	int i,j,nr=0;
	freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);
	scanf("%d",&n);
	for (i=1; i<=n; i++)
		scanf("%d",&v[i]);
	qsort(v,n+1,sizeof(v[0]),compar);
	for (i=1; i<=n; i++)
		for (j=i+1; j<n-1; j++)
			nr=nr+caut(v[i]+v[j],j,n)-j;
	printf("%d",nr);
}