Cod sursa(job #1431016)

Utilizator LegionHagiu Stefan Legion Data 8 mai 2015 22:59:26
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
int a[801];
int main()
{
	ifstream in("nrtri.in");
	ofstream out("nrtri.out");
	int i, n,j,x,y,mij,maxim,tot=0;
	in >> n;
	for (i = 1;i <= n;i++)
	{
		in >> a[i];
	}
	sort(a + 1, a + n + 1);
	for (i = 1;i <= n;i++)
	{
		for (j = i + 1;j < n;j++)
		{
			x = j + 1;
			y = n;
			maxim = 0;
			while (x <= y)
			{
				mij = (x + y) / 2;
				if (a[mij] <= a[i] + a[j])
				{
					maxim = mij;
					x = mij + 1;
				}
				else
				{
					y = mij - 1;
				}
			}
			if (maxim != 0)
			{
				tot += maxim - j;
			}
		}
	}
	out << tot;
}