Cod sursa(job #1472943)

Utilizator alexandru.ghergutAlexandru-Gabriel Ghergut alexandru.ghergut Data 18 august 2015 10:34:42
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <fstream>
#include <algorithm>
using namespace std;

int binarySearch(int sum, int left, int right, int a[])
{
    int middle;
    while (right - left > 1)
    {
        middle = left + (right - left) / 2;
        if (a[middle] <= sum)
            left = middle;
        else
            right = middle;
    }

    return left;
}

int main()
{
    int N, i, j, result = 0;
    ifstream f("nrtri.in");
    f >> N;
    int a[N];
    for (i = 0; i < N; i++)
        f >> a[i];
    f.close();

    sort(a, a + N);

    for (i = 0; i < N - 2; i++)
        for (j = i + 1; j < N - 1; j++)
            result += binarySearch(a[i] + a[j], j, N, a) - j;

    ofstream g("nrtri.out");
    g << result;
    g.close();

    return 0;
}