Cod sursa(job #2293322)

Utilizator dragos99Homner Dragos dragos99 Data 30 noiembrie 2018 20:30:18
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.83 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;
    while(start < stop){
        mij = (start + stop) / 2;
        if(v[mij] < numar){
            start = mij + 1;
        }
        else{
            stop = mij;
        }
    }
    return mij;
}

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, sum);
        if(sum >= v[poz])
            sol += poz - j;
    }
}

g<<sol;

return 0;
}