Cod sursa(job #355629)

Utilizator alutzuAlexandru Stoica alutzu Data 11 octombrie 2009 19:49:00
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda cautb1 Marime 0.73 kb
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int NMAX = 805 ;

int n ;
int x [ NMAX ] ;

int caut ( int v )
{
	int pas = 1<<10 ;
	int i ;
	for ( i = 0 ; pas ; pas >>= 1 )
		if ( i+pas <= n && x[i+pas] < v ) 
			i+= pas ;
	return i ;
}

int main ( )
{
	freopen ( "nrtri.in" , "r" ,stdin ) ;
	freopen ( "nrtri.out" , "w" , stdout ) ;
	
	int i ,j , k ;	
	
	scanf ( "%d" , & n) ;
	
	for ( i =1 ; i <= n ; i ++ )
		scanf ( "%d" , & x[i] ) ;
	
	sort ( x+1 , x+n+1 ) ;
	int nr = 0 ;
	for ( i = 1 ; i < n-1 ; i ++ )
		for ( j = i+1 , k = i +2 ; j < n ; j ++ )
		{
			while ( ( k <= n ) && x[i]+x[j]>=x[k] ) k++ ;
			nr += ( k - j - 1 ) ;
		}
	printf ( "%d" , nr ) ;
	return 0 ;
}