Cod sursa(job #2493246)

Utilizator NeacsuMihaiNeacsu Mihai NeacsuMihai Data 16 noiembrie 2019 10:58:36
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <iostream>
#include <fstream>

using namespace std;


int v[802];

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

    int n, i, nr, s, z, p, u, mij;
    bool ok;

    fin>>n;


    v[n+1]=60001;

    for(i=1; i<=n; i++) fin>>v[i];

    nr=0;
    for(i=1; i<=n-2; i++)
    {
        for(z=i+1; z<=n-1; z++)
        {
            s=v[i]+v[z];

            //cout<<"s= "<<s<<"\n";

            p=z+1;
            u=n;
            ok=0;

            while(p<=u && ok==0)
            {
                mij=(p+u)/2;

                if(v[mij] <= s && v[mij+1] > s) ok=1;
                else if(v[mij] > s) u=mij-1;
                else if(v[mij+1] <=s) p=mij+1;
            }

            //cout<<"i= "<<i<<"\nz= "<<z<<"\nmij= "<<mij<<"\nok= "<<ok<<"\n\n";

            if(ok==1) nr=nr+mij-z;
        }
    }

    fout<<nr;
}