Cod sursa(job #2215131)

Utilizator DawlauAndrei Blahovici Dawlau Data 21 iunie 2018 08:15:22
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

inline int binSearch(const vector <int> &Arr, const int &lft, const int &rgt) {

	int low = rgt + 1, high = Arr.size() - 1, pos = rgt;

	while (low <= high) {

		int mid = low + ((high - low) >> 1);

		if (Arr[mid] <= Arr[rgt] + Arr[lft]) {

			pos = mid;
			low = mid + 1;
		}
		else high = mid - 1;
	}

	return pos - rgt;
}

int main() {

	int N;
	fin >> N;

	vector <int> Arr;
	Arr.resize(N);

	for (int idx = 0; idx < N; ++idx)
		fin >> Arr[idx];

	sort(Arr.begin(), Arr.end());

	int cnt = 0;
	for (int low = 0; low < N - 2; ++low)
		for (int high = low + 1; high < N - 1; ++high) 
			cnt += binSearch(Arr, low, high);
	fout << cnt;
}