Cod sursa(job #754197)

Utilizator gener.omerGener Omer gener.omer Data 31 mai 2012 23:08:28
Problema Numarare triunghiuri Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <iostream>

using namespace std;

#define NMAX 805

int A[NMAX];

int main(){
	ifstream in("nrtri.in");
	ofstream out("nrtri.out");
	int N;
	in >> N;
	for(int i = 0; i < N; ++i)
		in >> A[i];
	vector<int> v (A, A + N);
	sort(v.begin(), v.end());
	int sz = N;
	
	vector<int>::iterator upper;
	int nr = 0;
	
	for(int i = 0; i < sz; ++i)
		for(int j = i + 1; j < sz; ++j){
			int s = v[i] + v[j];
			upper = upper_bound(v.begin(), v.end(), s);
			int l = (upper - v.begin());
			for(int k = 0; k < l; ++k)
				if(
				   k != i && k != j    &&
				   v[i] + v[j] >= v[k] &&
				   v[i] + v[k] >= v[j] &&
				   v[j] + v[k] >= v[i]
				   )
					++nr;
		}
			
	out << nr / 3;
	
	return 0;
}