Cod sursa(job #1690877)

Utilizator Debuger33Numarul1 Debuger33 Data 16 aprilie 2016 05:32:43
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <fstream>
#include <algorithm>
using namespace std ;
ifstream fin("nrtri.in") ;
ofstream fout("nrtri.out") ;

int cauta(int v[] , int n , int val)
{
	int st = 1 , dr = n + 1 ;
	while(st < dr)
	{
		int mid = st + (dr - st) / 2 ;
		if(v[mid] < val)
		{
			st = mid + 1 ;
		}
		else
		{
			dr = mid ;
		}
	}
	return st ;
}

int main()
{
	int n , v[900] ;
	fin >> n ;
	for(int i = 1 ; i <= n ; i ++)
	{
		fin >> v[i] ;
	}
	sort(v + 1 , v + n + 1) ;
	long long nr = 0 ;
	for(int j = 2 ; j <= n ; j ++)
	{
		for(int k = j + 1 ; k <= n ; k ++)
		{
			int it = cauta(v , n , v[k] - v[j]) ;
			if(it < j)
			{
				nr += (j - it) ;
			}
		}
	}
	fout << nr ;
	fin.close() ;
	fout.close() ;
	return 0 ;
}