Cod sursa(job #1521836)

Utilizator Vladut-Vlad Panait Vladut- Data 10 noiembrie 2015 21:24:23
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <fstream>
#include <algorithm>
#define MAXN 805

using namespace std;

ifstream fin("nrtri.in");
ofstream fout("nrtri.out");

int n, v[MAXN];
int sol;

void caut_bin(int v1, int v2, int l, int r, int a, int b)
{
	if (l > r)
		return;
	while (l <= r)
	{
		int m = (l + r) >> 1;
		int m1 = m;
		if (a + b >= v[m])
		{
			sol++;
			while (a + b >= v[--m] && m != v1 && m != v2)
			{
				sol++;
			}
			while (a + b >= v[++m1] && m1 != v1 && m1 != v2 && m1 <= n)
			{
				sol++;
			}
			l=r+1;
		}
		else
		{
			r = m - 1;
		}
	}
}

int main()
{
	fin >> n;
	for (int i = 1; i <= n; i++)
	{
		fin >> v[i];
	}

	sort(v + 1, v + n + 1);

	for (int i = 1; i <= n; i++)
	{
		for (int j = i + 1; j <= n; j++)
		{
			caut_bin(i, j, j + 1, n, v[i], v[j]);
		}
	}

	fout << sol;

	fin.close();
	fout.close();

	return 0;
}