Cod sursa(job #611178)

Utilizator SteveStefan Eniceicu Steve Data 31 august 2011 06:30:06
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <fstream.h>

int N, v[900], i, j, nr = 0, auxiliar, auxiliar2;

void citire ()
{
	ifstream fin ("nrtri.in");
	fin >> N;
	for (i = 0; i < N; i++)
	{
		fin >> v[i];
	}
	fin.close ();
}

int c_binara (int val, int capat)
{
	int i, step;
	for (step = 1; step <= capat; step <<= 1);
	for (i = 0; step; step >>= 1)
	{
		if (i + step < capat && v[i + step] <= val) i += step;
	}
	return i;
}

void qsort (int l1, int l2)
{
	int pivot = 0, l1a = l1, l2a = l2;
	if (l1 >= l2) return;
	while (l1 < l2)
	{
		if (v[l1] > v[l2])
		{
			auxiliar = v[l1];
			v[l1] = v[l2];
			v[l2] = auxiliar;
			if (pivot)
			{
				pivot = 0;
				l2--;
			}
			else
			{
				pivot = 1;
				l1++;
			}
		}
		else
		{
			if (pivot) l1++;
			else l2--;
		}
	}
	qsort (l1a, l1 - 1);
	qsort (l1 + 1, l2a);
}

void treaba (int index)
{
	for (i = 1; i < index; i++)
	{
		auxiliar = v[index] - v[i];
		auxiliar2 = c_binara (auxiliar, i);
		while (v[auxiliar2] == auxiliar) auxiliar2--;
		while (v[auxiliar2] + v[i] >= v[index] && auxiliar2 > 0) auxiliar2--;
		if (v[auxiliar2] + v[i] >= v[index]) nr = nr + i;
		else nr = nr + i - auxiliar2 - 1;
	}
}

void scriere ()
{
	ofstream fout ("nrtri.out");
	fout << nr;
	fout.close ();
}

int main ()
{
	citire ();
	if (N < 3)
	{
		scriere ();
		return 0;
	}
	qsort (0, N - 1);
	for (j = 2; j < N; j++)
	{
		treaba (j);
	}
	scriere ();
	return 0;
}