Cod sursa(job #2378732)

Utilizator cristiifrimIfrim Cristian cristiifrim Data 12 martie 2019 16:22:00
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

int v[801], n;

void citire() {
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> v[i];
    sort(v + 1, v + n + 1);
}

int cautbin(int x) {

    int i, pas;
    for(pas = 1; pas <= n; pas >>= 1);
    for(i = 0; pas; pas <<= 1) {
        if(i + pas < n && v[i + pas] <= x)
            i += pas;
    }
    return i;
}

int triunghiuri() {
    int sol = 0;
    for(int i = 1; i <= n - 2; ++i)
        for(int j = i + 1; j < n; ++j) {
            int s = v[i] + v[j];
            if(s >= v[cautbin(v[j+1])]) sol++;
        }
    return sol;
}

int main() {
    citire();
    cout << triunghiuri();
    cout.close();
}