Cod sursa(job #2979508)

Utilizator catalinmarincatalinmarin catalinmarin Data 15 februarie 2023 11:52:33
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
int v[801];
int CautBin(int vec[], int left, int right, int elem){
    int rezultat = 0;
    int mid = (left+right)/2;
    while (left <= right){
         mid = (left+right)/2;
        if (elem < v[mid])
            right = mid-1;
        else {
            left = mid+1;
            rezultat = mid;
        }
    }
    return rezultat;
}
int main(){
    int n;
    fin >> n;
    for (int i = 1; i <= n; i++){
        fin >> v[i];
    }
    sort (v+1, v+1+n);
    int NrTriunghiuri = 0;
    for (int i = 1; i <= n; i++){
        for (int j = i+1; j <= n; j++) {
            int SumaLaturi = v[i] + v[j];
            int RezultatCautareBin = CautBin(v, j+1, n, SumaLaturi);
            if (RezultatCautareBin != 0)
                NrTriunghiuri += RezultatCautareBin - j;
        }
    }
    fout << NrTriunghiuri;
    return 0;
}