Cod sursa(job #203943)

Utilizator AthanaricCirith Gorgor Athanaric Data 20 august 2008 22:40:27
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <stdio.h>
#include <stdlib.h>
struct interval
{
	int a,b;
};
interval v[850];
int compar(const void*p, const void*q)
{
	interval *pp=(interval*)p, *qq=(interval*)q;
	interval u=*pp, v=*qq;
	if (u.a<v.a)
		return -1;
	if (u.a>v.a)
		return 1;
	return u.a-v.a;
}
int main()
{
	int n,i,j,aux,count=0,s,d,m;
	freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);
	scanf("%d",&n);
	for (i=1; i<=n; i++)
		scanf("%d",&v[i].a);
	qsort(v,n,sizeof(v[0]),compar);
	for (i=1; i<n; i++)
		for (j=i+1; j<=n; j++)
		{
			s=j; d=n; 
			while (s!=d)
			{
				m=(s+d)/2;
				if ((v[m].a+v[i].a>=v[j].a)&&(v[m].a+v[j].a>=v[i].a)&&(v[i].a+v[j].a>=v[m].a))
					s=m+1;
					else d=m-1;
			}
			count=count+(s-j);
		}
	printf("%d",count);
}