Cod sursa(job #180001)

Utilizator ghiutaalexGhiuta Alex ghiutaalex Data 16 aprilie 2008 15:48:58
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.62 kb
#include<stdio.h>
#include<stdlib.h>
int v[1000],n,i,j,r;
int cmp(const void*a,const void*b)
	{return *(int*)a-*(int*)b;}
int cb(int x,int y)
{int m=(x+y)/2;
 while(x<=y)
	 if(v[m]<=v[i]+v[j]) return m;
	 else if(v[m]<v[i]+v[j]) {x=m+1;
				  m=(x+y)/2;}
	      else {y=m-1;
		    m=(x+y)/2;}
}
int main()
{int t;
 FILE*f=fopen("nrtri.in","r");
 FILE*g=fopen("nrtri.out","w");
 fscanf(f,"%d",&n);
 for(i=0;i<n;i++)
	fscanf(f,"%d",&v[i]);
 qsort(v,n,sizeof(v[0]),cmp);
 for(i=0;i<n-2;i++)
	for(j=1;j<n-1;j++)
		{t=cb(j,n);
		 r+=t-j;}
 fprintf(g,"%d",r-1);
 fcloseall();
 return 0;
}