Cod sursa(job #754200)

Utilizator gener.omerGener Omer gener.omer Data 31 mai 2012 23:17:34
Problema Numarare triunghiuri Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 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, lower;
	int nr = 0;
	
	for(int i = 0; i < sz; ++i)
		for(int j = i + 1; j < sz; ++j){
			upper = upper_bound(v.begin(), v.end(), v[i] + v[j]);
			lower = lower_bound(v.begin(), v.end(), max(v[i], v[j]) - min(v[i], v[j])); 
			int u = (upper - v.begin()), l = (lower - v.begin());
			
			for(int k = l; k < u; ++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;
}