Cod sursa(job #569548)

Utilizator alexdmotocMotoc Alexandru alexdmotoc Data 1 aprilie 2011 18:07:53
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <iostream>
#include <fstream>
using namespace std;

#define nmax 805

int n , x[nmax] , cont = 0 ;

int bin_search (int i , int j)
{
	int st = 1 , dr = n , mid;
	
	while (st < dr - 1)
	{
		mid = (st + dr) / 2;
		
		if (x[i] + x[j] >= x[mid] && x[mid] + x[i] >= x[j] && x[j] + x[mid] >= x[i])
			st = mid;
		else dr = mid;
	}
	
	if (x[i] + x[dr] >= x[j] && x[j] + x[dr] >= x[i] && x[i] + x[j] >= x[dr])
		return 1;
	//else if (x[st] + x[i] >= x[j] && x[j] + x[i] >= x[st] && x[st] + x[j] >= x[i])
		//return 1;
	return 0;
}
int main()
{
	ifstream f ("nrtri.in");
	ofstream g ("nrtri.out");
	
	f >> n;
	
	for (int i = 1 ; i <= n ; ++i)
		f >> x[i];
	
	sort (x + 1 , x + n + 1);
	
	for (int i = 1 ; i < n ; ++i)
	{
		for (int j = i + 1 ; j <= n ; ++j)
			if (bin_search(i , j))
				cont++;
	}
	
	g << cont;
	
	return 0;
}