Cod sursa(job #2035311)

Utilizator buzandanBuzan Dan Alexandru buzandan Data 9 octombrie 2017 10:40:40
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <fstream>
#include <algorithm>
using namespace std;

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

int n,a[802];
int CautareBinara(int l,int r,int val);
int main()
{
    fin >> n;
    int counter = 0;
    for(int i = 0; i < n; i++)
        fin >> a[i];
    sort(a,a + n);
    for(int i = 0; i < n; i++)
        for(int j = i + 1; j < n; j++)
            if(a[i] + a[j] <= a[n - 1] && i != CautareBinara(0,n - 1,a[i] + a[j]) && j != CautareBinara(0,n - 1,a[i] + a[j])){
                counter ++;
                //fout << a[i] <<' ' <<  a[j] << ' ' << a[CautareBinara(0,n - 1,a[i] + a[j])] << '\n';
            }
    fout << counter;
}

int CautareBinara(int l,int r,int val)
{


    int m, n = l;

    while (l < r){
        m = (l + r) / 2;
        if (a[m] <= val)
            l = m + 1;
        else
            r = m;
    }

    m = (l + r) / 2;
    if (a[m] > val)
       -- m;
    return m;
}