Cod sursa(job #2836654)

Utilizator andreea_chivuAndreea Chivu andreea_chivu Data 20 ianuarie 2022 18:14:33
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

int v[801];

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

    int n;
    fin >> n;

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

    sort(v, v+n);

    int cnt = 0;
    for(int a = 0; a < n - 2; a++){
        for(int b = a+1; b < n - 1; b++){
            int s = v[a] + v[b];
            int st = b + 1, dr = n - 1, poz = -1;
            while(st <= dr){
                int mij = (st + dr)/2;
                if(v[mij] <= s){
                    poz = mij;
                    st = mij + 1;
                }else{
                    dr = mij - 1;
                }
            }
            if(poz != -1)
                cnt += poz - b;
        }
    }

    fout << cnt;
    fin.close();
    fout.close();
    return 0;
}