Cod sursa(job #394954)

Utilizator toniobFMI - Barbalau Antonio toniob Data 11 februarie 2010 20:34:05
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <fstream>
using namespace std;
#include <algorithm>

ifstream in ( "nrtri.in" );
ofstream out ( "nrtri.out" );

int N, v [ 1 << 10 ], cnt;

bool comp ( int a, int b )
{
	return a < b;
}

/*void BS ( int I, int J )
{
	for ( int i = N; i > J; --i )
		if ( v [ i ] >= v [ I ] && v [ i ] >= v [ J ] && v [ i ] <= v [ I ] + v [ J ] )
		{
			cnt += i - J;
			break;
		}
}*/

void BS ( int I, int J )
{
	int i, lg,logN;
	for (logN = 1; logN <= N; logN <<= 1);
	for (lg = logN, i = 0; lg; lg >>= 1)
		if (i + lg <= N &&  v [ i + lg ] >= v [ I ] && v [ i + lg ] >= v [ J ] && v [ i + lg ] <= v [ I ] + v [ J ])
			i += lg;
	if ( v [ i ] >= v [ I ] && v [ i ] >= v [ J ] && v [ i ] <= v [ I ] + v [ J ] )
			cnt += i - J;
}

int main ()
{
	in >> N;
	for ( int i = 1; i <= N; ++i )
		in >> v [ i ];
	
	sort ( v + 1, v + N + 1, comp );
	
	for ( int i = 1; i < N; ++i )
		for ( int j = i + 1; j <= N; ++j )
			BS ( i, j );
	
	out << cnt;
	
	return 0;
}