Cod sursa(job #3171622)

Utilizator LucasSecaraSecara Lucas Victor LucasSecara Data 19 noiembrie 2023 10:38:16
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

int cauta(int i, int j, int n, int v[]){
    int st=j+1, dr=n;
    int mij;
    while(st<=dr){
        mij = (st+dr)/2;
        if (v[mij]<=v[i]+v[j] && (v[mij+1]>v[i]+v[j] || mij == n)){
            return mij;
        }
        else if (v[mij]<=v[i]+v[j] && v[mij+1]<=v[i]+v[j]){
            st = mij+1;
        }
        else {
            dr = mij-1;
        }
    }
    return 0;
}

int v[801], n, s=0;
int main() {
    fin >> n;
    for (int i=1; i<=n; i++){
        fin >> v[i];
    }
    sort(v+1, v+n+1);
    for (int i=1; i<=n; i++){
        for (int j=i+1; j<=n; j++){
            int p = cauta(i, j, n, v);
            if (p!=0){
                s++;
            }
        }
    }
    fout << s;
    return 0;
}