Cod sursa(job #2277709)

Utilizator mihaicivMihai Vlad mihaiciv Data 6 noiembrie 2018 19:02:51
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

ifstream f("nrtri.in");
ofstream g("nrtri.out");

int cauta(int st, int dr, int val, int v[]) {


    if (st <= dr) {
        if (st == dr) {
            return st;
        } else {
            int mij = (st + dr) / 2;
            if ( val <= v[mij] ) {
                return cauta(st, mij, val, v);
            } else {
                return cauta(mij + 1, dr, val, v);
            }
        }
    }

}


int main() {



    int n;

    f >> n;

    int v[n];

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

    int answer = 0;

    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            int diff = v[j] - v[i];
            int sum = v[i] + v[j];

            int pleft = cauta(0, n - 1, diff, v);
            int pright = cauta(0, n - 1, sum, v);

            answer += (pright - pleft );


        }
    }

    g << answer / 6;

    return 0;
}