Pagini recente » Cod sursa (job #1514712) | Cod sursa (job #937585) | Cod sursa (job #760960) | Cod sursa (job #11365) | Cod sursa (job #2495852)
#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;
}