Cod sursa(job #2468769)

Utilizator dey44andIoja Andrei-Iosif dey44and Data 5 octombrie 2019 22:09:28
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 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, total;

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;
}

int Binary_Search(int l1, int l2)
{
    int sol = -1;
    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 = midd;
            st = midd + 1;
        }
        else dr = midd - 1;
    }
    return sol;
}

void Solve()
{
    for(int i = 1; i <= N - 2; i++)
        for(int j = i + 1; j <= N - 1; j++)
        {
            //out << i << " " << j << " -> ";
            int local = Binary_Search(i, j);
            //out << local << " " << local - j<< "\n";
            if(local != -1)
                total += local - j;

        }
    out << total;
}

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