Cod sursa(job #1888227)

Utilizator Rocamadour1497Alexandru Martiniuc Rocamadour1497 Data 21 februarie 2017 23:15:49
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;
int n, a[800], i, j, nr = 0;
ifstream f("nrtri.in");
ofstream g("nrtri.out");
bool verif(int a, int b, int c)
{
	return ((a + b >= c) && (a + c >= b) && (b + c >= a));
}

bool bin(int st, int dr,int x,int y)
{
	while (st < dr)
	{
		int m = st / 2 + dr / 2;
		if (verif(a[m], x, y)) return 1;
		if (a[m] <= y) st = m+1;
		else dr = m - 1;

	}
	return 0;
}

int main()
{

	f >> n;
	for (i = 0; i < n; i++)
		f >> a[i];
	sort(a, a + n);
	for (i = 0; i < n - 2; i++)
	{
		for (j = i + 1; j < n - 1; j++)
		{
			nr += bin(j + 1, n - 1, a[i], a[j]);
		}
	}
	g << nr;
}