Cod sursa(job #462077)

Utilizator deneoAdrian Craciun deneo Data 9 iunie 2010 18:23:45
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
	vector<long> v(5000);
	vector<long>::iterator it1, it2;
	long i, n, j, nrsol=0;
	freopen("nrtri.in", "rt", stdin);
	freopen("nrtri.out", "wt", stdout);
	scanf("%ld", &n);
	for(i=0; i<n; ++i)
		scanf("%ld", &v[i]);
	v.resize(n);
	sort(v.begin(), v.end());
	for(i=0; i<n; ++i)
		for(j=0; j<n; ++j)
			if(j!=i)
			{
				it1=lower_bound(v.begin(), v.end(), max(v[i], v[j])-min(v[i], v[j]));
				it2=upper_bound(v.begin(), v.end(), v[i]+v[j]);
				nrsol+=it2-it1;
				if(*it2==0)
					nrsol--;
				if(*it1<=v[i] && *it2>v[i])
					nrsol--;
				if(*it1<=v[j] && *it2>v[j])
					nrsol--;
				
			}
	printf("%ld", nrsol/6);
	return 0;
}