Cod sursa(job #2898846)

Utilizator Minea_TheodorMinea Theodor Stefan Minea_Theodor Data 7 mai 2022 12:47:19
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <bitset>
#include <cmath>
#include <queue>

using namespace std;

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

int CautBin(vector <int> &a, int left, int val)
{
    int right = a.size() - 1;
    int pos = -1;
    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (a[mid] <= val)
        {
            pos = mid;
            left = mid + 1;
        }
        else right = mid - 1;
    }
    return pos;
}

int main()
{
    int n;
    fin >> n;
    vector <int> v(n);
    for (int i = 0; i < n; i++)
        fin >> v[i];
    sort(v.begin(), v.end());
    int nrtri = 0;
    for (int i = 0; i < n - 2; i++)
        for (int j = i + 1; j < n - 1; j++) {
            int p = CautBin(v, j + 1, v[i] + v[j]);
            if (p != -1)
                nrtri += p - j;
        }
    fout << nrtri << "\n";
    fin.close();
    fout.close();
    return 0;
}
/// 1-3-4-5