Cod sursa(job #2357811)

Utilizator MateiCatalinUrsache Matei MateiCatalin Data 27 februarie 2019 19:03:07
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.69 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(a[n]<=a[i]+a[j])
            {
                tr=tr+(n-j);
            }
            else
            {
                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;
}