Mai intai trebuie sa te autentifici.

Cod sursa(job #2035314)

Utilizator Dragos123Tatar Dragos Vlad Dragos123 Data 9 octombrie 2017 10:41:57
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <fstream>
#include <algorithm>
using namespace std;

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

const int Dim = 801;
int a[Dim];
int n;

void ReadArray();
void Rezolvare();
int BinarySearch(int l, int r, int vl, int vr);

int main()
{
    ReadArray();
    Rezolvare();
}

void ReadArray()
{
    fin >> n;
    for(int i = 1; i <= n; ++i)
        fin >> a[i];
}

void Rezolvare()
{
    sort (a + 1, a + n + 1);
    int nr = 0;
    for(int i = 1; i <= n - 2; ++i)
        for(int j = i + 1; j <= n - 1; ++j)
        {
            if (BinarySearch(j + 1, n, a[i], a[j]) != 0)
                nr += BinarySearch(j + 1, n, a[i], a[j]) - j;
        }
    fout << nr;
}

int BinarySearch(int l, int r, int vl, int vr)
{
    int mid;
    int s = vl + vr;
    while (l <= r)
    {
        mid = ( l + r ) / 2;
        if (a[mid] <= s)
            return mid;
        if (a[mid] > s)
            r = mid - 1;
    }
    return 0;
}