Cod sursa(job #2293327)

Utilizator dragos99Homner Dragos dragos99 Data 30 noiembrie 2018 20:54:35
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 kb
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
    ifstream f("nrtri.in");
    ofstream g("nrtri.out");

long n;
vector<long> v;

long cautare_binara(long start, long stop, long numar){
    long mij = (start + stop) / 2;
    while(start < stop){
        if(v[mij] <= numar){
            start = mij + 1;
        }
        else{
            stop = mij;
        }
        mij = (start + stop) / 2;
    }
    if(v[mij] == numar)
        return mij;
    return mij - 1;
}

int main()
{
f>>n;
long x;
for(long i = 0 ; i < n ; i++){
    f>>x;
    v.push_back(x);
}
sort(v.begin(), v.end());

long sol = 0;

for(long i = 0 ; i < n - 2 ; i++){
    for(long j = i + 1 ; j < n - 1 ; j++){
        long sum = v[i] + v[j];
        long poz = cautare_binara(j + 1, n - 1, sum);
        if(sum >= v[poz] && poz > j)
            //g<<i<<" "<<j<<" "<<poz<<'\n';
           sol += poz - j;
    }
}

g<<sol;

return 0;
}