Cod sursa(job #2978274)

Utilizator rapidu36Victor Manz rapidu36 Data 13 februarie 2023 16:51:49
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <fstream>

using namespace std;

void sortare(int v[], int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        int pmin = i;
        for (int j = i + 1; j < n; j++)
        {
            if (v[j] < v[pmin])
            {
                pmin = j;
            }
        }
        if (pmin != i)
        {
            swap(v[i], v[pmin]);
        }
    }
}

int caut_bin(int v[], int n, int val)
{
    int st = 0, dr = n - 1, rez = -1;
    while (st <= dr)
    {
        int m = (st + dr) / 2;
        if (v[m] <= val)
        {
            rez = m;
            st = m + 1;
        }
        else
        {
            dr = m - 1;
        }
    }
    return rez;
}

int main()
{
    ifstream in("nrtri.in");
    ofstream out("nrtri.out");
    int n;
    in >> n;
    int v[n];
    for (int i = 0; i < n; i++)
    {
        in >> v[i];
    }
    sortare(v, n);
    int nrt = 0;
    for (int i = 0; i + 2 < n; i++)
    {
        for (int j = i + 1; j + 1 < n; j++)
        {
            ///k = pozitia utimului elem. din v care e <= (v[i]+v[j])
            int k = caut_bin(v, n, v[i] + v[j]);
            nrt += k - j;
        }
    }
    out << nrt;
    in.close();
    out.close();
    return 0;
}