Cod sursa(job #1197430)

Utilizator dalv_1337Pasita Vlad dalv_1337 Data 11 iunie 2014 22:39:21
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.54 kb
#include <fstream>
#include <algorithm>
using namespace std;

const int nMax = 801;

int v[nMax];

inline int bin_search(int st,int dr,int x)
{
	int mij;
	while (st<=dr) {
		mij=(st+dr)>>1;
		v[mij]>x ? dr=mij-1 : st=mij+1;
	}
	return dr;
}

int main()
{
	ifstream fIn("nrtri.in");
	ofstream fOut("nrtri.out");

	int n;
	fIn>>n;
	for (int i=1; i<=n; ++i) fIn>>v[i];

	sort(v+1,v+n+1);

	int sol=0;
	for (int j,i=1; i<n; ++i)
		for (j=i+1; j<=n; ++j)
			sol+=bin_search(j,n,v[i]+v[j])-j;

	fOut<<sol;

	return 0;
}