Cod sursa(job #518650)

Utilizator ms-ninjacristescu liviu ms-ninja Data 2 ianuarie 2011 14:28:02
Problema Numarare triunghiuri Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <fstream>
using namespace std;

int v[801];


/*int binar(int s, int ls)
{
	int ld=n;
	
	while(ls<=ld)
	{
		int mijloc=(ls+ld)/2;
		if((v[mijloc]<=s && v[mijloc+1]>s) || (mijloc==n && v[mijloc]<=s))
			return mijloc;
		else
			if(v[mijloc]<=s && v[mijloc+1]<=s)
				ls=mijloc+1;
			else
				ld=mijloc-1;
	}
}*/

int main()
{
	ifstream fin("nrtri.in");
	ofstream fout("nrtri.out");
	int i, j,nr,n;
	fin>>n;
	
	for(i=1;i<=n;++i)
		fin>>v[i];
	
	sort(v+1,v+n+1);
	nr=0;
	for(i=1;i<=n-2;++i)
		for(j=i+1;j<=n-1;++j)
			{
				int k=j+1;
				while(v[i]+v[j]>=v[k] && k<=n)
				{
					++nr;
					++k;
				}
			
			}
			
			//nr+=binar(v[i]+v[j],j)-j;
		
		fout<<nr;
		return 0;
}