Cod sursa(job #2495852)

Utilizator sebimihMihalache Sebastian sebimih Data 19 noiembrie 2019 21:37:39
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;
int const N = 1000;

ifstream fin("nrtri.in");
ofstream fout("nrtri.out");

int bs(int n, int Latura1, int Latura2, int LungimeBat[])
{
	int inceput = 0;
	int sfarsit = n - 1;
	int PozitieValida = 0;

	while (inceput <= sfarsit)
	{
		int mijloc = (inceput + sfarsit) / 2;

		if (LungimeBat[mijloc] <= Latura1 + Latura2)
		{
			inceput = mijloc + 1;
			PozitieValida = mijloc;
		}
		else
		{
			sfarsit = mijloc - 1;
		}
	}

	return PozitieValida;
}

int main()
{
	/** 3 laturi formeaza un triughi daca:
		* a + b > c
		* b + c > a
		* a + c > b

		** toate laturile triunghiului sunt diferite de 0
	*/

	int n, LungimeBat[N];
	fin >> n;
	int contor = 0;

	for (int i = 0; i < n; i++)
	{
		fin >> LungimeBat[i];
	}

	sort(LungimeBat, LungimeBat + n);
	
	for (int i = 0; i < n - 2; i++)  // Nu vrem sa luam ultimele 2 nr din sir pt ca acestea nu vor avea alta latura cu care sa formeze un triunghi
	{
		contor += bs(n, LungimeBat[i], LungimeBat[i + 1], LungimeBat) - (i + 1);
	}

	fout << contor;
}