Cod sursa(job #1792315)

Utilizator crazylamaRiclea Andrei crazylama Data 30 octombrie 2016 12:27:32
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <fstream>
#include <vector>

using namespace std;

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

int n;
vector<int> v;

int CautareBinara(int st, int dr, int x)
{
    if (st <= dr)
    {
        int mij = st + (dr - st) / 2;
        if (v[mij] == x)
            return mij;
        else if (v[mij] > x)
            return CautareBinara(st, mij - 1, x);
        else
            return CautareBinara(mij + 1, dr, x);
    }
    return dr;
}

void QuickSort(int st, int dr)
{
    if (st < dr)
    {
        int i = st, j = dr, x = v[st];
        while (i < j)
        {
            while (i < j && v[j] >= x)
                j--;
            v[i] = v[j];
            while (i < j && v[i] <= x)
                i++;
            v[j] = v[i];
        }
        v[i] = x;
        QuickSort(st, i - 1);
        QuickSort(i + 1, dr);
    }
}

int main()
{
    int sum = 0;
    f >> n;
    v.resize(n);
    for (int i = 0; i < n; ++i)
        f >> v[i];
    QuickSort(0, n - 1);
    /*
        for (int i = 0; i < n; ++i)
            g << v[i] << " ";
        g << endl;
    */
    for (int i = 0; i < n - 1; ++i)
        for (int j = i + 1; j < n; ++j)
            if (v[i] + v[j] <= v[n - 1])
                sum += CautareBinara(j, n - 1, v[i] + v[j]) - j;
    g << sum;
    return 0;
}