Cod sursa(job #2216015)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 24 iunie 2018 15:58:06
Problema Numarare triunghiuri Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream f("nrtri.in");
ofstream g("nrtri.out");

const int NMAX = 825;

int a[NMAX];

int n;

bool OK(int a, int b, int c)
{
	return (a + b >= c && b + c >= a && a + c >= b);
}

int bs(int p1, int p2, int dr = n)
{
	int st = p2 + 1;
	int sol = 0;
	while(st <= dr)
	{
		int mij = (dr + st) / 2;
		if(OK(a[p1], a[p2], a[mij]))
			sol = mij, st = mij + 1;
		else
			dr = mij - 1;
	}
	if(OK(a[p1], a[p2], a[sol]))
		return sol - p2;
	return 0;
}

int main()
{
	f >> n;
	for(int i = 1; i <= n; i++)
		f >> a[i];
	int sol = 0;
	sort(a + 1, a + 1 + n);
	for(int i = 1; i < n - 1; i++)
		for(int j = i + 1; j < n; j++)
			sol += bs(i, j);
	g << sol;
}