Cod sursa(job #2521503)

Utilizator RAdu2005Radu Stoiana RAdu2005 Data 10 ianuarie 2020 23:16:30
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <fstream>

ifstream fin("nrtri.in");
ofstream fout("nrtri.out");

using namespace std;

long long n,i,j,S,nrt,mij,r,l,k,x,y,HHA,ok;
int a[1007];

int main()
{
    fin >> n;
    for (i=1;i<=n;i++){
        fin >> a[i];
    }
    for (i=1;i<=n;i++){
        for (j=i;j<=n;j++){
            if (a[i]>a[j]){
                swap (a[i],a[j]);
            }
        }
    }
    for (i=1;i<=n-2;i++){
        for (j=i+1;j<=n-1;j++){
            S=a[i]+a[j];
            if (S<a[j+1])
                nrt=nrt+0;
            if (S>a[n])
                nrt=nrt+(n-j);
            else{
                l=j+1;
                r=n;
                ok=0;
                while (l<=r && ok==0){
                    mij=l+(r-l)/2;
                    if (a[mij]<S){
                        if (a[mij+1]>=S || mij==r){
                            k=mij;
                            ok=1;
                        }
                        else
                            l=mij+1;
                    }
                    else
                        r=mij-1;
                }
                nrt=nrt+(k-j);
            }
        }
    }
    fout << nrt;
    return 0;
}