Cod sursa(job #570085)

Utilizator alexdmotocMotoc Alexandru alexdmotoc Data 2 aprilie 2011 15:16:07
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 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 = j + 1 , dr = n , mid , nr;
	
	while (st < dr - 1)
	{
		mid = (st + dr) / 2;
		
		if (x[i] + x[j] >= x[mid])
			st = mid;
		else dr = mid - 1;
	}
	
	if (x[dr] <= x[i] + x[j]) 
		nr = dr;  
	
	else if (x[st] <= x[i] + x[j]) 
		nr = st;
	
	else 
		nr = st - 1; 
	return nr;
}
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)
			cont += bin_search(i , j) - j;
	
	g << cont;
	
	return 0;
}