Cod sursa(job #1042164)

Utilizator titusuTitus C titusu Data 26 noiembrie 2013 17:16:24
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

int n, v[1000];

bool maimic(int x,int y)
{
	if(x < y)
		return true;
	return false;
}

void taraneala()
{
	int c = 0;
	for(int i = 1 ; i < n - 1 ; ++i)
		for(int j = i + 1 ; j < n ; ++j)
			for(int k = j + 1 ; k <= n ;k ++)
				if(v[i]+v[j] >= v[k])
					c++;
	cout << c << endl;
}

int main()
{
	fin >> n;
	for(int i=1 ; i <= n ;++i)
		fin >> v[i];
	sort(v + 1 , v + n + 1, maimic);
	//for(int i=1 ; i <= n ;++i)	cout << v[i]  << " ";	cout << endl;
	//taraneala();
	v[n+1] = 1000000000;
	int c = 0;
	for(int i = 1 ; i < n - 1 ; ++i)
		for(int j = i + 1 ; j < n ; ++j)
		{
			int st = j + 1, dr = n+1;
			while(st<dr)
			{
				int mijloc = (st+dr) / 2;
				if(v[i]+v[j] < v[mijloc])
					dr = mijloc;
				else
					st = mijloc+1;
			}
			//cout << i << " " << j << " " << dr << endl;
			c += dr-j-1;
		}
	fout << c;
	return 0;
}