Cod sursa(job #2356732)

Utilizator MateiCatalinUrsache Matei MateiCatalin Data 26 februarie 2019 21:10:12
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.38 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)
                {
                    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;
}