Cod sursa(job #3160427)

Utilizator PetraPetra Hedesiu Petra Data 23 octombrie 2023 22:47:09
Problema Numarare triunghiuri Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

vector<int> v;
int n, cont=0;
int cautare_binara(int st, int dr, int x)
{
    if (st > dr) return -1;
    int mijl = (st + dr) / 2;
    if (v[mijl] <= x && v[mijl+1] > x) return mijl;
    if (v[mijl] > x) return cautare_binara(0, mijl, x);
    else return cautare_binara(mijl + 1, dr, x);
}
int main()
{
    fin >> n;
    for (int i = 0; i < n; i++)
    {
        int x;
        fin >> x;
        v.push_back(x);
    }
    sort(v.begin(), v.end());
    v.push_back(0x3f);
    for (int i = 0; i < n-1; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            /// setam i, j laturile => cautam cea mai mica latura v[k] <= v[i] + v[j]
            int k = cautare_binara(0, n - 1, v[i]+v[j]);
            if (k != -1) cont += (k - j);
        }
    }
    fout << cont;
    return 0;
}