Cod sursa(job #518647)

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

int v[801],n, i, j, nr;


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");
	
	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)
			nr+=binar(v[i]+v[j],j)-j;
		
		fout<<nr;
		return 0;
}