Cod sursa(job #2036752)

Utilizator cri25Berbecariu Crina cri25 Data 11 octombrie 2017 08:14:00
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <fstream>
#include <algorithm>
using namespace std;

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

int n, a[801];

int Search(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 rez{0};
    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j)
            rez += Search(j + 1, n, a[i] + a[j]);

    fout << rez << '\n';
}

int Search(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;
}