Cod sursa(job #3351932)

Utilizator NunumNunum nunum Nunum Data 22 aprilie 2026 15:02:06
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
int bin(int v[], int a, int c, int b)
{
    int mid;
    while(a<c){
        mid=a+(c-a)/2;
        if(v[mid]<=b){
            a=mid+1;
        }
        else{
            c=mid;
        }
    }
    return a;
}
int bin2(int v[], int a, int c, int b)
{
    int mid;
    while(a<c){
        mid=a+(c-a)/2;
        if(v[mid]<b){
            a=mid+1;
        }
        else{
            c=mid;
        }
    }
    return a;
}
int main()
{
    int n,i,j,a,b,c,v[801],p,q,nr=0;;
    fin>>n;
    for(i=1; i<=n; i++){
        fin>>v[i];
    }
    if(n<3){
        fout<<0;
    }
    else{
        for(i=1; i<=n;i++){
            for(j=i+1; j<=n; j++){
                if(v[i]>v[j]){
                    int aux= v[j];
                    v[j]=v[i];
                    v[i]=aux;
                }
            }
        }
        for(a=1; a<=n; a++){
            for(c=a+2; c<=n; c++){
                p=bin2(v,a+1,c,v[c]-v[a]);
                if(p<a+1)
                {
                    p=a+1;
                }
                q=bin(v,a+1,c,v[c]+v[a])-1;
                if(q>c-1){
                    q=c-1;
                }
                if(q>=p){
                    nr+=(q-p+1);
                }
            }
        }
    }
    fout<<nr;
}