Cod sursa(job #2538439)

Utilizator game_difficultyCalin Crangus game_difficulty Data 4 februarie 2020 19:07:47
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

int v[2001];

int cbin(int n1, int n2, int n)
{
    int pas, pos = n2 + 1;
    for (pas = 1 << 11; pas > 0; pas >>= 1)
        if (pos + pas <= n && (v[n1] < v[n2] + v[pos + pas] && v[n2] < v[n1] + v[pos + pas] && v[pos + pas] < v[n1] + v[n2]))
            pos += pas;
    return pos;
}

int main()
{
    int n, i, i0, i1, ans = 0;
    in >> n;
    for (i = 1; i <= n; i++)
        in >> v[i];
    sort(v + 1, v + n + 1);
    for (i = 1; i <= n - 2; i++)
        for (i0 = i + 1; i0 <= n - 1; i0++)
        {
            i1 = cbin(i, i0, n);
            if (v[i] < v[i0] + v[i1] && v[i0] < v[i] + v[i1] && v[i1] < v[i] + v[i0])
            {
                ans += i1 - i0;
                //out<<i<<' '<<i0<<' '<<i1<<'\n';
            }
        }
    out << ans;
}

// i + i0 > i1 && i + i1 > i0 && i0 + i1 > i
// v[i] + v[i0] > v[i1] && v[i] + v[i1] > v[i0] && v[i0] + v[i1] > v[i]