Cod sursa(job #118978)

Utilizator hadesgamesTache Alexandru hadesgames Data 28 decembrie 2007 18:10:35
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <stdio.h>
#include <stdlib.h>
int n,a[1000];
int compare( const void* a, const void* b ) {
   int* arg1 = (int*) a;
   int* arg2 = (int*) b;
   if( *arg1 < *arg2 ) return -1;
   else if( *arg1 == *arg2 ) return 0;
   else return 1;
 }           
int cauta(int x,int u, int s)
{
	int m;
	while (u<s)
	{
		m=(u+s)/2;
		if (a[m]<=x)
			u=m+1;
		else 
			s=m;
	}
	if (a[u]>x)
		return u;
	return n;
}
int main()
{
	FILE *in,*out;
	int nr=0,i,j;
	
	
	in=fopen("nrtri.in","r");
	out=fopen("nrtri.out","w");
	fscanf(in,"%d",&n);
	for (i=0;i<n;i++)
		fscanf(in,"%d",&a[i]);
	qsort(a,n,sizeof(a[0]),compare);
	for (i=0;i<n;i++)
		for (j=i+1;j<n-1;j++)
			nr+=cauta(a[i]+a[j],j,n-1)-j-1;
	fprintf(out,"%d\n",nr);
	fclose(in);
	fclose(out);
	return 0;
}