Cod sursa(job #2375411)

Utilizator igroitaGroita Igor igroita Data 8 martie 2019 09:05:33
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.66 kb
#include<fstream>
#include<algorithm>
using namespace std;

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

int n, l[804];

int cautare(int st, int dr) {
	int p = st, P = dr;
	while (st < dr) {
		int mid = (st + dr) / 2;
		if (l[mid] + l[p] >= l[P]) {
			dr = mid;
		}
		else {
			st = mid + 1;
		}
	}
	if (st == P) return 0;
	if (st == p) return P - p - 1;
	return P - st;
}


int main() {

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

	sort(l+1, l + n + 1);
	
	int nt = 0;
	for (int i = 1; i < n - 1; ++i) {
		for (int j = i + 2; j <= n; ++j){
			nt += cautare(i, j);
		}
	}

	fout << nt;
	


	return 0;
}