Cod sursa(job #486994)

Utilizator ChallengeMurtaza Alexandru Challenge Data 23 septembrie 2010 15:28:57
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <fstream>
#include <algorithm>

using namespace std;

const char InFile[]="nrtri.in";
const char OutFile[]="nrtri.out";
const int MaxN=805;

ifstream fin(InFile);
ofstream fout(OutFile);

int v[MaxN],n,nrtri;

int cauta_maimic(int x)
{
	int p=0;
	int u=n-1;
	int m;
	while(p<=u)
	{
		m=p+(u-p)/2;
		if(x<=v[m])
		{
			u=m-1;
		}
		else
		{
			p=m+1;
		}
	}
	if(v[p]>=x)
	{
		return p;
	}
	return -1;
}

int cauta_maimare(int x)
{
	int p=0;
	int u=n-1;
	int m;
	while(p<=u)
	{
		m=p+(u-p)/2;
		if(x<v[m])
		{
			u=m-1;
		}
		else
		{
			p=m+1;
		}
	}

	if(v[u]<=x)
	{
		return u;
	}
	return -1;
}

int main()
{
	fin>>n;
	for(register int i=0;i<n;++i)
	{
		fin>>v[i];
	}
	fin.close();

	sort(v,v+n);
	for(register int i=0;i<n;++i)
	{
		for(register int j=i+1;j<n;++j)
		{
			if(i!=j)
			{
				int mare=cauta_maimare(v[i]+v[j]);
				int mic=cauta_maimic(abs(v[j]-v[i]));
				if(mic<=mare && mic>-1 && mare>-1)
				{
					nrtri+=mare-mic+1;
					if(mic<=i && i<=mare)
					{
						--nrtri;
					}
					if(mic<=j && j<=mare)
					{
						--nrtri;
					}
				}
			}
		}
	}

	fout<<nrtri/3;
	fout.close();
	return 0;
}