Cod sursa(job #3140362)

Utilizator vozian.anghelinaAnghelina Vozian vozian.anghelina Data 5 iulie 2023 18:40:43
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 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 " << m << endl;
  //  cout << A[prim] << " + " << A[doi] << " ? " << A[m] << endl;

    if(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] << endl;
        return m;
    } 

    if(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] << endl;
        return m-1;
    } 

    if(l == r){
        return m-1;
    }

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

    if(A[prim] + A[doi] < A[m] && A[m] + A[prim] < A[doi] && A[m] + A[doi] < A[prim]){
        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;
}