Cod sursa(job #76194)

Utilizator a7893Nae Mihai a7893 Data 8 august 2007 20:31:52
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include<stdio.h>
#include<stdlib.h>
#define N 1000
int n,v[N];
void read()
{
	int i;
	scanf("%d",&n);
	for(i=0;i<n;i++)
		scanf("%d",&v[i]);
}
int maxim(const void *a,const void *b)
{
	return *(int*)a-*(int*)b;
}
int search(int i1,int j1)
{
	int p,u,i;
	u=n-1;
	for(i=u;i>j1;i--)
		if(v[i1]+v[j1]>=v[i])
			return i;
	return 0;
}
void solve()
{
	int i,j,nr=0,poz;
	qsort(v,n,sizeof(v[0]),maxim);
	for(i=0;i<n-2;i++)
		for(j=i+1;j<n-1;j++)
		{
			poz=search(i,j);
			if(poz)
				nr+=poz-j;
		}
	printf("%d\n",nr);
}
int main()
{
	freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);
	read();
	solve();
	return 0;
}