Cod sursa(job #1621569)

Utilizator adu18sptAndrei Mircea adu18spt Data 29 februarie 2016 20:01:51
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include<fstream>
#include<algorithm>
#include<iostream>
using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
unsigned n,a[1000],i,j,sum,c,nr;

unsigned step=1<<18,index;

unsigned cautbin(unsigned val,unsigned start);

int main()
{
	fin>>n;
	for(i=1;i<=n;i++)
	{
		fin>>a[i];
	}
	sort(a+1,a+n+1);
	
	for(i=1;i<n-1;i++)
	{
		for(j=i+1;j<n;j++)
		{
			sum=a[i]+a[j];
			
			c=cautbin(sum,j+1)+1;
			
			if(a[i] + a[j] >= a[c])
			nr++;
		}
	}
	fout<<nr;
	return 0;
}

unsigned cautbin(unsigned val,unsigned start)
{
	for(;step;step>>=1)
	{
		index=start+step;
		if(index>=n)
		continue;
		if(a[index]<val)
		start=index;
	}
	return start;	
}