Cod sursa(job #1415279)

Utilizator OrolesVultur Oroles Data 4 aprilie 2015 02:15:21
Problema Numarare triunghiuri Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <iostream>
#include <fstream>
#include <list>

int a[800];

void radixSort(int *v, int size)
{
	static const int BASE = 10;
	std::list<int> bucket[BASE];

	for ( int n = 1; n < 30000; n *= BASE )
	{
		int k = 0;
		for ( int i = 0; i < size; ++i )
		{
			bucket[(v[i]/n)%BASE].push_back(v[i]);
		}
		for ( int i = 0; i < BASE; bucket[i++].clear() )
		{
			for ( std::list<int>::iterator j = bucket[i].begin(); j != bucket[i].end(); ++j )
			{
				v[k++] = (*j);
			}
		}
	}
}

int isTriangle( int x, int y, int z )
{
	if ( x+y >= z && x+z >= y && y+z >= x )
	{
		return 1;
	}
	return 0;
}

int bsearch( int st, int dr, int val1, int val2 )
{
	while ( st <= dr )
	{
		int m = ( st + dr ) / 2;
		if ( isTriangle( val1, val2, a[m] ) )
		{
			st = m + 1;
		}
		else
		{
			dr = m - 1;
		}
	}
	return st;
}

int counttri( int *v, int size )
{
	int count = 0;
	for ( int i = 0; i < size - 2; ++i )
	{
		for ( int j = i+1; j < size - 1; ++j )
		{
			int poz = bsearch( j+1, size, v[i], v[j] );
			if ( poz > size )
			{
				continue;
			}
			count += poz - j - 1;
		}
	}
	return count;
}

int main( int argc, char* argv[] )
{
	std::ifstream input("nrtri.in");
	std::ofstream output("nrtri.out");
	
	int N;
	input >> N;
	for ( int i = 0; i < N; ++i )
	{
		input >> a[i];
	}
	radixSort( a, N );
	output << counttri( a, N ) << "\n";

	input.close();
	output.close();
	return 0;
}