Cod sursa(job #2444713)

Utilizator CostiVVoicu Costi CostiV Data 1 august 2019 10:22:04
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <fstream>
#include <algorithm>
using namespace std;

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

    int N;
    fin >> N;
    int i, v[805];
    for (i = 1; i <= N; ++i)
        fin >> v[i];
    sort(v + 1, v + N + 1);
    int nr = 0;
    for (i = 1; i <= N-2; ++i)
        for (int j = i + 1; j <= N-1; ++j){
            int l = 1, r = N, m;
            int s = v[i] + v[j], c = 0;
            while (l <= r){
                m = (l + r) / 2;
                if (v[m] == s){
                    ++nr;
                    break;
                }
                else{
                    if (v[m] < s){
                        c = m;
                        l = m + 1;
                    }
                    else
                        r = m - 1;
                }
            }
            nr += (c - j);
        }
    fout << nr;
    return 0;
}