Cod sursa(job #1560450)

Utilizator deresurobertoFMI - Deresu Roberto deresuroberto Data 2 ianuarie 2016 18:37:07
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
//Roberto Deresu - FMI
//Re :)
#include <fstream>
#include <algorithm>
#define nx 807
using namespace std;
int n, sol, v[807];

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

int BinarySearch(int v[], int pos, int value)
{
    int step = 1 << 10;

    while (step >>= 1)
    {
        if (pos + step < n && v[pos + step] <= value)
        {
            pos += step;
        }
    }

    return pos;
}

int main()
{
    fin >> n;

    for (int i = 0; i < n; i++)
    {
        fin >> v[i];
    }

    sort (v, v + n);

    for (int i = 0; i < n-2; i++)
    {
        for (int j = i + 1; j < n - 1; j++)
        {
            int pos = BinarySearch(v, j, v[i] + v[j]);

            sol += pos - j;
        }
    }

    fout << sol;

    return 0;
}