Cod sursa(job #3140372)

Utilizator vozian.anghelinaAnghelina Vozian vozian.anghelina Data 5 iulie 2023 19:34:59
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <bits/stdc++.h>
using namespace std;
int n, rs=0;
int A[1001];

int laturi3(int l, int r, int prim, int doi){
    int m = (l+r)/2;
   // cout << "m " << A[m] << endl;
   // cout << "left " << A[l] << " right " << A[r] <<endl;
   // cout << A[prim] << " + " << A[doi] << " ? " << A[m] << endl;

    if((l == r || l > r) && A[prim] + A[doi] >= A[m] && A[m] + A[prim] >= A[doi] && A[m] + A[doi] >= A[prim]){
    //    cout << A[prim] << " + " << A[doi] << " >= " << A[m] << "  |1 " << endl;
        return m;
    } 

    if((l == r || l > r)  && A[prim] + A[doi] >= A[m-1] && A[m-1] + A[prim] >= A[doi] && A[m-1] + A[doi] >= A[prim]){
     //   cout << A[prim] << " + " << A[doi] << " >= " << A[m-1] << "  |2 " << endl;
        return m-1;
    } 

    if((l == r || l > r) ){
     //   cout << A[prim] << " + " << A[doi] << " =" << A[m] << "  |3 " << endl;
        return 0; 
    }

    if(A[prim] + A[doi] >= A[m] && A[m] + A[prim] >= A[doi] && A[m] + A[doi] >= A[prim]){
     //   cout << A[prim] << " + " << A[doi] << " >=  " << A[m] << "  |4 " << endl;
        return laturi3(m+1, r, prim, doi);
    } 

    if(A[prim] + A[doi] < A[m]){
     //   cout << A[prim] << " + " << A[doi] << " <  " << A[m] << "  |5 " << endl;
        return laturi3(l, m-1, prim, doi);
    }

    return 0;

}

int main(){
    ifstream cin("nrtri.in");
    ofstream cout("nrtri.out");
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> A[i];
    }
    sort(A, A + n);

    for(int i=0; i<n-2; i++){
        for(int j=i+1; j<n-1; j++){
            rs += laturi3(j+1, n-1, i, j) - j;
           // cout << "rs devine " << rs << endl;
        }
    }
    cout << rs;
}