Cod sursa(job #29589)

Utilizator skyelHighScore skyel Data 9 martie 2007 16:58:16
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include<fstream.h>

int n,a[1000];

int divide(int p,int u)
	{
	int i,k,r,x=a[p];
	i=p;
	k=u;
	while(i<k)
		{
		while(i<k && a[k]>=x)	k--;

		a[i]=a[k];

		while(i<k && a[i]<=x)	i++;

		a[k]=a[i];

		}
	a[i]=x;
	return i;
	}
void qsort(int p,int u)
	{
	int m=divide(p,u);
	if(m-1>p)
		qsort(p,m-1);
	if(m+1<u)
		qsort(m+1,u);
	}

int bsearch(int s,int k,int x)
	{
	int m=(s+k)/2;
	if(s>k)
		return s;
	if(x==a[m])
		{
		while(a[m]==x) m++;
		return m-1;
		}
	else
		{
		if(x>a[m])
			{
			if(x<a[m+1])
				return m;
			return bsearch(m+1,k,x);
			}
		else
			return bsearch(s,m-1,x);

		}
	}

int main()
	{
	int i,j,s=0,k;
	ifstream fin("nrtri.in");
	ofstream fout("nrtri.out");
	fin>>n;
	for(i=1;i<=n;i++)
		fin>>a[i];
	qsort(1,n);
	for(i=1;i<n-1;i++)
		for(j=i+1;j<n;j++)
			{
			k=bsearch(j,n,a[i]+a[j]);
			s+=k-j;
			}
	fout<<s<<"\n";
	return 0;
	}