Mai intai trebuie sa te autentifici.

Cod sursa(job #430660)

Utilizator dacyanMujdar Dacian dacyan Data 31 martie 2010 11:19:47
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <fstream>
using namespace std;

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

int BinarySearch(int);
int a[801], n, i, j, v;
long long nr;

int main()
{
	fin >> n;
	for ( i = 0; i < n; i++)
		fin >> a[i];
	fin.close();
	
	sort(a, a + n);
	for ( i = 0; i < n; i++)
		for ( j = i; j < n - 1; j++)
		{
			v = BinarySearch(a[i] + a[j]); // returneaza cea mai mare valoare cre nu resp conditia
			if ( v != n - 1)
				nr += n - 1 - v;
		}
	fout << nr << '\n';
	//fout << BinarySearch(a[0] + a[1]);
	fout.close();
	return 0;
}

int BinarySearch(int v)
{
	int st = 0, dr = n - 1, mij;
	while ( st <= dr)
	{
		mij = (st + dr) / 2;
		if ( a[mij] == v) return mij - 1; // returneaza cea mai mare valoare cre nu resp conditia
		else
			if ( a[mij] > v) dr = mij - 1;
			if ( a[mij] < v) st = mij + 1;
	}
	return st;
}