Cod sursa(job #1971547)

Utilizator Marina23Oprea Marina Marina23 Data 20 aprilie 2017 15:46:04
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <fstream>
#include <algorithm>
using namespace std;

int N,i,Nr,St,Dr,Mij,Rez,Sum,A[801],j;

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

    fin>>N;
    for(i=1;i<=N;i++)
        fin>>A[i];
    sort(A+1,A+N+1);
    Nr=0;
    for(i=1;i<=N-2;i++)
        for(j=i+1;j<=N-1;j++)
        {
            Sum=A[i]+A[j];
            St=j+1;
            Dr=N;
            Rez=-1;
            while(St<=Dr)
            {
                Mij=(St+Dr)/2;
                if(A[Mij]<=Sum)
                {
                    Rez=Mij;
                    St=Mij+1;
                }//if
                else
                    Dr=Mij-1;
            }//while
            if(Rez!=-1)
                Nr+=Rez-j;
        }//for j
    fout<<Nr;

    fin.close ();
    fout.close();
    return 0;
}