Cod sursa(job #3175317)

Utilizator varzarigheorgheVarzari Gheorghe varzarigheorghe Data 25 noiembrie 2023 17:07:27
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

int main()
{
    int n, v[801], i, j, left, right, mid, ans = 0, poz;
    fin >> n;
    for (i = 0; i <= n; i ++) {
        fin >> v[i];
    }
    sort(v + 1 , v + n + 1);
    for (i = 0; i < n - 2; i ++) {
        for (j = i + 1; j < n - 1; j++) {
            left = j + 1;
            right = n - 1;
            poz = j;
            while (left <= right) {
                mid = (left + right) / 2;
                if (v[mid] <= v[i] + v[j]) {
                    left = mid + 1;
                    poz = mid;
                } else
                    right = mid - 1;
            }
        ans += poz - j;
        }
    }
    fout << ans;
    return 0;

}