Cod sursa(job #331576)

Utilizator emilia.ciobanuCiobanu Emilia Maria Silvia emilia.ciobanu Data 14 iulie 2009 16:17:27
Problema Numarare triunghiuri Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.26 kb
#include<stdio.h>
#define N 800

int Partitie ( int*, int , int);
void Quicksort ( int*, int, int );
int BinSh ( int*, int );

int n;

int main()
{
	int A[N], i, j, poz, nr = 0, sum, aux = 1 ;

	freopen( "nrtri.in", "r", stdin );
	freopen( "nrtri.out", "w", stdout );	

	scanf("%d", &n );

	for ( i = 0 ; i < n ; i++ )
		scanf ("%d", &A[i] );

	Quicksort( A, 0, n-1 );
	

	for ( i = 0 ; i < n-2 ; i++ )
		for ( j = i+1 ; j < n-1 ; j++ )
		{
			sum = A[i]+A[j];
			while( sum > A[j] )
			{
				poz = BinSh(A, sum);
				sum--;
				if ( poz != -1 )
					nr++;
			}
		}	

	printf ("%d", nr);

	return 0;
}

int BinSh ( int *A, int x )
{
	int low = 0, high = n, mid;
	while ( low < high ) 
	{
		mid = low + ( high - low) / 2;
		if ( A[mid] < x )
			low = mid + 1;
		else
			high = mid;
	}
	if ( (low < n ) && ( A[low] == x ) )
		return low;
	else return -1;
}

	
void Quicksort ( int *A, int st, int dr )
{
	int p;
	if ( st < dr )
	{
		p = Partitie( A, st, dr );
		Quicksort( A, st, p );
		Quicksort ( A, p+1, dr );
	}
}

int Partitie ( int *A, int st, int dr )
{
	int pivot = A[st], i = st-1, j = dr + 1;
	while( 1 )
	{
		do { i++; } while ( A[i] < pivot );
		do { j--; } while ( A[j] > pivot );
		if ( i < j )
		{
			int aux = A[i];
			A[i] = A[j];
			A[j] = aux;
		}
			else return j;
	}
}