Cod sursa(job #2356784)

Utilizator MateiCatalinUrsache Matei MateiCatalin Data 26 februarie 2019 21:37:34
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <fstream>

#include <algorithm>



using namespace std;



int main()

{

    ifstream f("nrtri.in");

    ofstream g("nrtri.out");

    int n,i,j,y,a[801],tr=0,dr,st,mij;

    f>>n;

    for(i=1;i<=n;i++)

    {

        f>>a[i];

    }

    sort(a+1,a+n+1);

    for(i=1;i<=n-2;i++)

    {

        for(j=i+1;j<=n-1;j++)

        {

            st=j+1;

            dr=n;

            if(st==dr)

            {

                if(a[i]+a[j]>=a[st])

                {

                    tr++;

                }

            }

            while(st<dr)

            {

                mij=(st+dr)/2;

                if(a[mij]==a[i]+a[j]+1)

                {   y=mij;

                    while(a[y]==a[i]+a[j]+1)

                    {

                        y--;

                    }

                    tr=tr+(y-j);

                    st=dr;

                }

                else

                {

                    if(a[mij]<a[i]+a[j]+1)

                    {

                        st=mij;

                    }

                    else

                    {

                        dr=mij;

                    }

                    if(st+1==dr)

                    {

                        tr=tr+(st-j);

                        st=dr;

                    }

                }

            }

        }

    }

    g<<tr;

    f.close();

    g.close();

    return 0;

}