Cod sursa(job #1202311)

Utilizator IulianBoboUAIC Boboc Iulian IulianBobo Data 27 iunie 2014 17:05:26
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.57 kb
#include <fstream>
#include <algorithm>
using namespace std;

bool compare(int a,int b){ return (a<b);}
int main()
{
	ifstream f("nrtri.in");
	ofstream g("nrtri.out");
	int n,i,j,count=0;
	long v[801];
	f>>n;
	for(i=0;i<n;i++) f>>v[i];
	sort(v,v+n,compare);
	for(i=0;i<n-2;i++)
		for(j=i+1;j<n-1;j++)
		{
			int s=j+1,d=n-1,m,maxim=j;
			while(s<=d)
			{
				m=(s+d)/2;
				if(v[m]<=v[i]+v[j])
				{
					if(m>maxim) maxim=m;
					s=m+1;
				}
				else
					d=m-1;
			}
			count=count+maxim-j;
		}
	g<<count;
	f.close();
	g.close();
	return 0;
}