Cod sursa(job #732214)

Utilizator Coman95coman cosmin Coman95 Data 9 aprilie 2012 22:09:47
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <fstream>
using namespace std;

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

int a[801];
int n;
int i, j, aux;
int nrt;

int Search( int st, int dr );

int main()
{
	fin >> n;
	for( i = 0; i < n; ++i )
		fin >> a[i];
	for( i = 0; i < n - 1; ++i )
		for( j = i + 1; j < n; ++j )
			if( a[i] > a[j] )
			{
				aux = a[i];
				a[i] = a[j];
				a[j] = aux;
			}
	int x;
	for( i = 0; i < n - 2; ++i)
		for( j = i + 1; j < n - 1; ++j)
		{
			x = Search( 0, n-1 );
			if( x == i + j && j < x)
				nrt += x - j + 1;
			else
				nrt += x - j - 1;
		}
	fout << nrt + 1;		
	fin.close();
	fout.close();
	return 0;
}

int Search(int st, int dr)
{
  int mij;
  mij = ( st + dr ) / 2;
  while( st <= dr)
  {
    if(( a[mij] <= a[i] + a[j] && a[mij+1] > a[i]+a[j] ) || ( a[mij] <= a[i] + a[j] && mij == n-1))
		return mij;
	else
		if( a[mij] <= a[i] + a[j] && a[mij+1] <= a[i] + a[j])
			st = mij + 1; 
		else 
			dr = mij - 1; 
		mij = (st + dr) / 2;
  }
  return 0;
}