Cod sursa(job #2035321)

Utilizator MihneaEnceanMihnea Encean MihneaEncean Data 9 octombrie 2017 10:45:33
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <fstream>
#include <algorithm>

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

int n, a[801];

int BinarySearch(int l, int r, int s);

int main()
{
    fin >> n;
    for (int i = 1; i <= n; ++i)
        fin >> a[i];
    std::sort(a + 1, a + 1 + n);
    int cnt = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j)
            cnt += BinarySearch(j + 1, n, a[i] + a[j]);

    fout << cnt;
}

int BinarySearch(int l, int r, int s)
{
    int m, p{-1}, pi{l};
    while (l <= r)
    {
        m = (l + r) / 2;
        if (a[m] <= s)
            l = m + 1, p = m;
        else
            r = m - 1;
    }

    if (p == -1)
        return 0;
    else
        return p - pi + 1;
}