Cod sursa(job #199199)

Utilizator cipPaduraru Ciprian - Ionut cip Data 17 iulie 2008 14:48:01
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 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]));
}
void swap(int& x, int& y)
{
	int temp;
	temp = x;
	x = y;
	y = temp;
}// end swap()

void selectionSort(int arr[], int size)
{
	int indexOfMin, pass, j;

	for (pass = 0; pass < size - 1; pass++)
	{
		indexOfMin = pass;

		for (j = pass + 1; j < size; j++)
			if (arr[j] < arr[indexOfMin])
				indexOfMin = j;

		swap(arr[pass], arr[indexOfMin]);
	}
}// end selectionSort()



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

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


	selectionSort(Numbers,n);

	//varianta 1 : cautare binara
	int iCount = 0;
	for (int i = 0 ; i < n - 2 ; i++)
		for (int j = i + 1 ; j < n - 1; j ++)
		{
			result = -1;
			cautBin2(j + 1, n-1 , Numbers[i] + Numbers[j]);
			if (result != -1)
				iCount += result - j;
		}
		

	printf("%d\n",iCount);
	return 0;
}