Cod sursa(job #243917)

Utilizator mottyMatei-Dan Epure motty Data 14 ianuarie 2009 11:21:25
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include<stdio.h>

#include<stdlib.h>

#define M 801

int n,v[M];

void citire()
{
	freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);
	int i=0;
	scanf("%d",&n);
	while (++i<=n)
		scanf("%d",&v[i]);
}

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;
}

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;//fiindca se iese cu un k prost ( primul care nu e bun )
		}
	}
	printf("%d",perechi);
}

int main()
{
	citire();
	qsort(v+1,n,sizeof(v[0]),compar);
	calcul();
	return 0;
}