Cod sursa(job #715359)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 17 martie 2012 02:06:28
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <fstream>
#include <algorithm>
#include <cmath>

using namespace std;

int n, a[805];
long long sol;

void Read()
{
	ifstream f("nrtri.in");
	f>>n;
	int i;
	for (i=1; i<=n; i++)
		f>>a[i];
	f.close();
}

int cautare(int x)
{
	int st = 1, dr = n, m;
	while (st<=dr)
	{
		m = (st+dr)/2;
		if (a[m]<=x && (a[m+1] > x || m == n-1))
			return m;
		else
		{
			if (a[m]<=x && a[m+1] <= x)
			{
				st = m+1;
			}
			else
				dr = m-1;
		}
	}
	return 0;
}

void Solve()
{
	int i, j, poz;
	sort(a+1, a+n+1);
	for (i=1; i<=n; i++)
	{
		for (j=i+1; j<=n; j++)
		{
			poz = cautare(a[i] + a[j]);
			if (poz && poz!=i && poz!=j && a[i]+a[j] >= a[poz] && a[i] + a[poz] >= a[j] && a[j] + a[poz] >= a[i])
				sol++;
		}
	}
}

void Write()
{
	ofstream g("nrtri.out");
	g<<sol<<"\n";
	g.close();
}

int main()
{
	Read();
	Solve();
	Write();
	return 0;
}