Cod sursa(job #3042141)

Utilizator SSKMFSS KMF SSKMF Data 4 aprilie 2023 09:26:38
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

ifstream cin ("nrtri.in");
ofstream cout ("nrtri.out");

vector <int> sir;

int Cautare_Binara (int stanga , int dreapta , int valoare)
{
    if (sir[stanga] > valoare)
        return -1;

    int pozitie = dreapta;
    while (stanga <= dreapta)
    {
        int mijloc = (stanga + dreapta) / 2;

        if (sir[mijloc] <= valoare)
            stanga = mijloc + 1 , pozitie = mijloc;
        else
            dreapta = mijloc - 1;
    }

    return pozitie;
}

int main ()
{
    int lungime;
    cin >> lungime;

    sir.resize(lungime + 1);
    for (int indice = 1 ; indice <= lungime ; indice++)
        cin >> sir[indice];

    sort(sir.begin() , sir.end());

    long long triunghiuri = 0;
    for (int indice_1 = 1 ; indice_1 < lungime - 1 ; indice_1++)
        for (int indice_2 = indice_1 + 1 ; indice_2 < lungime ; indice_2++)
        {
            int pozitie = Cautare_Binara(indice_2 + 1 , lungime , sir[indice_1] + sir[indice_2]);
            if (pozitie != -1)
                triunghiuri += pozitie - indice_2;
        }

    cout << triunghiuri;
    cout.close(); cin.close();
    return 0;
}