Cod sursa(job #2467748)

Utilizator dey44andIoja Andrei-Iosif dey44and Data 4 octombrie 2019 23:35:29
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <fstream>
#include <algorithm>

#define input "nrtri.in"
#define output "nrtri.out"
#define NMAX 805

using namespace std;

ifstream in(input);
ofstream out(output);

int laturi[NMAX], N, sol;

void Read_Data()
{
    in >> N;
    for(int i = 1; i <= N; i++)
        in >> laturi[i];
    sort(laturi + 1, laturi + 1 + N);
}

bool Check_Sol(int a, int b, int c)
{
    if(a + b >= c && a + c >= b && c + b >= a)
        return true;
    return false;
}

bool Binary_Search(int l1, int l2)
{
    int st = l2 + 1, dr = N;
    while(st <= dr)
    {
        int midd = (st + dr) / 2;
        if(Check_Sol(laturi[l1], laturi[l2], laturi[midd]))
        {
            //out << l1 << " " << l2 << " " << midd << "\n";
            sol++;
            st = midd + 1;
        }
        else dr = midd - 1;
    }
}

void Solve()
{
    for(int i = 1; i <= N - 2; i++)
        for(int j = i + 1; j <= N - 1; j++)
            Binary_Search(i, j);
    out << sol;
}

int main()
{
    Read_Data();
    Solve();
    return 0;
}