Cod sursa(job #1048480)

Utilizator gabriel.badeaGabriel Badea gabriel.badea Data 5 decembrie 2013 21:59:23
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <iostream>
#include <algorithm>
using namespace std;


int n, v[1000];

bool minim(int x,int y)
{
	if(x < y)
		return true;
	return false;
}

int main()
{
	freopen("nrtri.in", "r", stdin);
	freopen("nrtri.out", "w", stdout);

	cin >> n;
	for(int i=1 ; i <= n ;++i)
		cin >> v[i];
	sort(v+1 , v+n+1, minim);
	v[n+1] = 1000000000;

	int c = 0;

	for(int i = 1 ; i < n - 1 ; ++i)
		for(int j = i + 1 ; j < n ; ++j)
		{
			int st = j + 1, dr = n+1;
			while(st<dr)
			{
				int mijloc = (st+dr) / 2;
				if(v[i]+v[j] < v[mijloc])
					dr = mijloc;
				else
					st = mijloc+1;
			}
			c += dr-j-1;
		}

		cout << c;

		return 0;
}