Cod sursa(job #2311158)

Utilizator aurelionutAurel Popa aurelionut Data 2 ianuarie 2019 18:18:46
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <fstream>
#include <algorithm>

using namespace std;

int n, v[810];
int ans = 0;

void Read()
{
	ifstream fin("nrtri.in");
	fin >> n;
	for (int i = 1;i <= n;++i)
		fin >> v[i];
	sort(v + 1, v + n + 1);
	fin.close();
}

int BinarySearch(int x, int y, int val)
{
	int left = x, right = y, mid, poz = x - 1;
	while (left <= right)
	{
		mid = (left + right) / 2;
		if (v[mid] <= val)
		{
			poz = mid;
			left = mid + 1;
		}
		else
			right = mid - 1;
	}
	return poz;
}

void Solve()
{
	int poz;
	for (int i = 1;i <= n - 2;++i)
		for (int j = i + 1;j <= n - 1;++j)
		{
			poz = BinarySearch(j + 1, n, v[i] + v[j]);
			ans += poz - j;
		}
}

void Write()
{
	ofstream fout("nrtri.out");
	fout << ans << "\n";
	fout.close();
}

int main()
{
	Read();
	Solve();
	Write();
	return  0;
}