Cod sursa(job #2497438)

Utilizator Marius7122FMI Ciltea Marian Marius7122 Data 22 noiembrie 2019 17:47:37
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <iostream>
#include <fstream>
#include <algorithm>
 
using namespace std;
int const N = 1000;
 
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
 
int bsUltimul(int n, int LungimeBat[], int SumaLaturilor)
{
	int sol = 0;
	int pas = 1 << 10;
 
	while (pas > 0)
	{
		if (sol + pas < n && LungimeBat[sol + pas] <= SumaLaturilor)
		{
			sol += pas;
		}
		pas /= 2;
	}
 
	return sol;
}
 
int bsPrimul(int n, int LungimeBat[], int SumaLaturilor)
{
	int sol = bsUltimul(n, LungimeBat, SumaLaturilor - 1);
	if (sol < SumaLaturilor)
	{
		sol++;
	}
 
	return sol;
}
 
int main()
{
	/** Pentru a forma un triunghi:
		* a + b >= c
		* b + c >= a
		* a + c >= b
{1}
		[abs(i - j); i + j]
		cautam binar numerele din interval
	*/
 
	int n;
	fin >> n;
 
	int contor = 0;
	int LungimeBat[N];
 
	for (int i = 0; i < n; i++)
	{
		fin >> LungimeBat[i];
	}
 
	sort(LungimeBat, LungimeBat + n);
 
	for (int i = 0; i < n - 2; i++) // Pentru ultimele 2 nr din sir nu vom putea forma un triunghi
	{
		for (int j = i + 1; j < n - 1; j++)  // Mergem pana la penultima cifra
		{
			int Dreapta = bsUltimul(n, LungimeBat, LungimeBat[i] + LungimeBat[j]);
			int Stanga = j + 1;
 
			int NrInInterval = Dreapta - Stanga + 1;
 
			contor += NrInInterval;
		}
	}
 
	fout << contor;
}