Cod sursa(job #567963)

Utilizator alexdmotocMotoc Alexandru alexdmotoc Data 30 martie 2011 18:10:14
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <iostream>
#include <fstream>
using namespace std;

int n , x[805] , st , dr , cont = 0 , mid;

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);
	
	st = 1;
	dr = n;
	
	while (dr - st > 1)
	{
		mid = (st + dr) / 2;
		
		if (x[st] + x[dr] >= x[mid] && x[mid] + x[st] >= x[dr] && x[mid] + x[dr] >= x[st])
		{
			cont++;
			st = mid;
		}
		
		else dr = mid + 1;
	}
	
	st = 1;
	dr = n;
	
	while (dr - st > 1)
	{
		mid = (st + dr) / 2;
		
		if (x[st] + x[dr] >= x[mid] && x[mid] + x[st] >= x[dr] && x[mid] + x[dr] >= x[st])
		{
			cont++;
			dr = mid;
		}
		
		else st = mid;
	}
	
	g << cont;
	
	return 0;
}