Cod sursa(job #1470846)

Utilizator AlexandraaaaMereu Alexandra Alexandraaaa Data 12 august 2015 14:28:07
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

int n, v[802];

int caut(int x,int ls) {
	int lo, hi, m;
	lo = ls;
	hi = n;
	while (hi - lo > 1){
		m = (lo + hi) / 2;
		if (v[m] <= x)
			lo = m;
		else
			hi = m;
	}
	return lo;
}

int main() {
	ifstream f("nrtri.in");
	ofstream g("nrtri.out");

	int i, j, k, s = 0;
	f >> n;
	for (i = 0; i < n; ++i)
		f >> v[i];
	sort(v, v + n - 1);

	for (i = 0; i < n-2; ++i) {
		for (j = i + 1; j < n - 1; ++j) {
			if (v[i] + v[j] < v[j + 1])
				continue;
			k = caut(v[i] + v[j], j + 1);
			s += k - j;
		}
	}
	g << s;
	f.close();
	g.close();
	return 0;
}