Cod sursa(job #715363)

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

using namespace std;

int n, a[805], 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-1; i++)
	{
		for (j=i+1; j<n; j++)
		{
			poz = (int)(upper_bound(a+j+1, a+n+1, a[i] + a[j]) - a-j-1);
			sol+=poz;
		}
	}
}

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

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