Cod sursa(job #561071)

Utilizator tudor0013tudor petrescu tudor0013 Data 18 martie 2011 20:42:58
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

const int N = 805;

int v[N],n;

int sort_function( const void *a, const void *b)
{
	int x = *(int*)a, y = *(int*)b;
	if(x<y)
		return -1;
	if(x>y)
		return 1;
	return 0;
}

int caut(int x)
{
	int i,pas=1<<9;
	for(i=0 ; pas ; pas/=2)
		if(i+pas<=n && v[i+pas]<=x)
			i += pas;
	return i;
}

int main()
{
   int  i,j,k,r=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[1], N, sizeof(v[0]), sort_function);
   for(i=1;i<n;i++)
		for(j=i+1;j<=n;j++)
		{
			k = caut(v[i]+v[j]);
			r += k-j;
		}
   printf("%d\n",r);
   return 0;
}