Cod sursa(job #394803)

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

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

const int NMax = 1 << 10;
int N, v [ NMax ], cnt;

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

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

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