Cod sursa(job #199171)

Utilizator cipPaduraru Ciprian - Ionut cip Data 17 iulie 2008 12:38:02
Problema Numarare triunghiuri Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>

#define MAXD	100000

int Numbers[MAXD], n , q ,x ,result;

void cautBin1(int i, int j ,int x)
{
	if (i <= j)
	{
		int mijloc = i + ((j - i)>>1);
		if (Numbers[mijloc] <= x)
		{
			if (Numbers[mijloc] == x)
				result = mijloc;

			cautBin1(mijloc + 1 , j, x);
		}
		else
			cautBin1(i , mijloc - 1, x);
	}
}

void cautBin2(int i, int j, int x)
{
	if (i <= j)
	{
		int mijloc = i + ((j - i)>>1);
		if (Numbers[mijloc] <= x)
		{
			result = mijloc;
			cautBin2(mijloc + 1 , j , x);
		}
		else
			cautBin2(i, mijloc - 1 , x);
	}
}

void cautBin3(int i , int j , int x)
{
	if (i <= j)
	{
		int mijloc = i + ((j - i)>>1);
		if (Numbers[mijloc] < x)
			cautBin3(mijloc + 1, j, x);
		else
		{
			result = mijloc ;
			cautBin3(i, mijloc - 1 , x);
		}
	}
}

bool CanBeTriangle(int i ,int j ,int k)
{
	return ( (Numbers[i] <= Numbers[j] + Numbers[k] ) && (Numbers[j] <= Numbers[i] + Numbers[k]) && (Numbers[k] <= Numbers[i] + Numbers[j]));
}

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

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

	//varianta 1 : cautare bruta
	int iCount = 0;
	for (int i = 0 ; i < n - 2 ; i++)
		for (int j = i + 1 ; j < n - 1; j ++)
			for (int k = j + 1 ; k < n ; k++)
				if (CanBeTriangle(i,j,k) == true)
					iCount++;
	printf("%d\n",iCount);



	return 0;
}