Cod sursa(job #3160428)

Utilizator PetraPetra Hedesiu Petra Data 23 octombrie 2023 22:51:35
Problema Numarare triunghiuri Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.89 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 i, int j)
{
    int st = j + 1, dr = n, k = -1;
    while(st <= dr)
    {
        int mij = (st+dr) / 2;
        if (v[i]+v[j] >= v[mij])
        {
            k = mij;
            st = mij+  1;
        }
        else dr = mij - 1;
    }
    if (k == -1) return 0;
    return k - j;
}
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++)
        {
            cont += cautare_binara(i, j);
        }
    }
    fout << cont;
    return 0;
}