Cod sursa(job #3141276)

Utilizator not_anduAndu Scheusan not_andu Data 13 iulie 2023 14:02:39
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.66 kb
/*

Fie laturile unui triunghi: a, b, c

! Realtia unui Triunghi: a + b > c

*/


#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

#define INFILE "nrtri.in"
#define OUTFILE "nrtri.out"
#define VMAX 801

ifstream fin (INFILE);
ofstream fout (OUTFILE);

int n;
int aux, v[VMAX];

void afisare(){

    for(int i = 1; i <= n; ++i){
        fout << v[i] << " ";
    }

    fout << '\n';

}

bool triunghi(int a, int b, int c){
    
    return (a + b >= c) &&
           (b + c >= a) &&
           (c + a >= b);

}

int upper_bound(int valoare){

    int st = 1, dr = n;

    while(st < dr){

        int mij = (st + dr + 1) / 2;

        if(v[mij] <= valoare){
            st = mij;
        }
        else{
            dr = mij - 1;
        }

    }

    return st;

}

void rezolvare(){

    int st, dr, mij, cnt = 0, sol = 0;

    for(int i = 1; i < n; ++i){
        for(int j = i + 1; j <= n; ++j){

            st = j + 1, dr = n;
            sol = -1;

            while(st <= dr){

                mij = (st + dr) / 2;

                if(v[mij] <= v[i] + v[j] && sol < mij){
                    sol = mij;
                }
                if(v[mij] <= v[i] + v[j]){
                    st = mij + 1;
                }
                else{
                    dr = mij - 1;
                }

            }
            
            if(sol != -1){

                cnt += sol - j;

            }

        }
    }

    fout << cnt << '\n';

}

void read(){

    fin >> n;

    for(int i = 1; i <= n; ++i){
    
        fin >> v[i];

    }

    // afisare();

    sort(v + 1, v + n + 1);

    // afisare();

    rezolvare();

}

int main(){
    read();
    return 0;
}