Cod sursa(job #513034)

Utilizator thesilverhand13FII Florea Toma Eduard thesilverhand13 Data 14 decembrie 2010 22:47:08
Problema Numarare triunghiuri Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include<fstream>
#define maxd 802
#include<algorithm>
using namespace std;
long  a[maxd],n,nr,s;
ifstream f("nrtri.in");
ofstream g("nrtri.out");
void citire()
{
	int i;
	f>>n;
	for(i=1;i<=n;i++)
		f>>a[i];
}
int cautarebinara(long st,long dr,long x)
{
	long gasit=0,m;
	while(st<=dr&&gasit==0)
	{
		m=(st+dr)/2;
		if(a[m]<=x&&a[m+1]>x)
			return m;
		else
			if(a[m]<=x)
				st=m+1;
			else
				dr=m-1;
	}
		return -1;
		
}
void calculeaza()
{
	long  i,j,c;
	s=0;
	sort(a+1,a+n+1);
	a[n+1]=32000;
	//for(i=1;i<=n;i++)
		//g<<a[i]<<" ";
	//g<<"\n";
	for(i=1;i<=n-2;i++)
		for(j=i+1;j<=n-1;j++)
		{
			s=a[i]+a[j];
			c=cautarebinara(j+1,n,s);
			if(c>j)
				nr=nr+c-j;
	
	}

}
int main()
{
	citire();
	calculeaza();
	g<<nr;
	return 0;
}