Cod sursa(job #3141274)

Utilizator not_anduAndu Scheusan not_andu Data 13 iulie 2023 13:56:33
Problema Numarare triunghiuri Scor 45
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.75 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 sum = 0, indice, cnt = 0, indice_aux;

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

            sum = v[i] + v[j];

            indice = upper_bound(v[j]);

            while(!triunghi(v[i], v[j], v[indice])){
                --indice;
            }

            indice_aux = indice;

            while(triunghi(v[i], v[j], v[indice_aux])){
                if(indice_aux == i || indice_aux == j){
                    --cnt;
                }
                else{
                    // fout << "a: " << v[i] << "; b: " << v[j] << "; c: " << v[indice_aux] << '\n';
                }
                --indice_aux;
            }

            cnt += (indice - indice_aux);

        }
    }

    fout << cnt / 2 << '\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;
}