Cod sursa(job #1396789)

Utilizator bluespideyMarin Diana bluespidey Data 22 martie 2015 23:57:16
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

int n,i,nr,j,a,e,hi,lo,mid,v[801],b,c,d,r,sum;

int mod(int f)
{
    if(f<0)
        f*=(-1);
    return f;
}


int main()
{
    fin >> n;

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

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

    for(i = 1; i <= n;++i)
        for(j = i + 1; j <= n; ++j)
            {
                a = mod(v[i]-v[j]);
                b = v[j]+v[i];

                hi = n;
                lo = 1;

                while(lo<hi)
                    {
                        mid = lo + (hi-lo)/2;

                        if(v[mid]<a)
                            lo = mid+1;
                        else if(v[mid]>a)
                            hi = mid-1;
                        else {while(v[mid-1]==a)
                                    --mid;
                                break;}
                    }
                while((v[mid]>a)&&(mid>1))
                    --mid;
                if(v[mid]<a)
                    ++mid;
                d = mid;

                hi = n;
                lo = 1;

                while(lo<hi)
                    {
                        mid = lo + (hi-lo)/2;

                        if(v[mid]<b)
                            lo = mid+1;
                        else if(v[mid]>b)
                            hi = mid-1;
                        else {while(v[mid+1]==b)
                                    ++mid;
                                break;}
                    }
                while((v[mid]<b)&&(mid<n))
                    ++mid;
                if(v[mid]>b)
                    --mid;

                e = mid;

                if(e-d-1>0)
                    nr+=e-d-1;

            }
    fout << nr/2;

    return 0;
}