Cod sursa(job #936942)

Utilizator tibiletsKoos Tiberiu Iosif tibilets Data 9 aprilie 2013 09:42:31
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include<stdio.h>
int N,a[2000],i,j,k,n,m;
int pivot(int i,int j)
{int i1=0,j1=1,x;
 while(i<j)
 {if(a[i]>a[j])
	 {x=a[i];a[i]=a[j];a[j]=x;
	  x=i1;i1=j1;j1=x;}
  i+=i1;j-=j1;}
 return i;}
void sort(int i,int j)
{if(i<j)
 {int k=pivot(i,j);
  sort(i,k-1);
  sort(k+1,j);}}
int main()
{freopen("nrtri.in","r",stdin);
freopen("nrtri.out","w",stdout);
scanf("%d",&N);
for(i=0;i<N;++i)
	scanf("%d",&a[i]);
sort(0,N-1);
for(i=0;i<N-2;++i)
	for(j=i+1;j<N-1;++j)
	{int x=a[i]+a[j],s=j+1,d=N-1;k=j;
	 while(s<=d)
	 {m=(s+d)/2;
	  if(x<a[m])
		  d=m-1;
	  else
		 {k=m;
		  s=m+1;}}
	 n+=k-j;}
printf("%d",n);
return 0;
}