Cod sursa(job #1965564)

Utilizator workwork work work Data 14 aprilie 2017 14:38:46
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream F("nrtri.in");
ofstream G("nrtri.out");

int n, mij, st, dr, step, k, v[802], mini,m;

int main()
{
    F >> n;
    for(int i = 1; i <= n; ++ i)
        F >> v[i];
    sort(v + 1, v + n + 1);
    for(int i = 1; i < n - 1; ++ i)
        for(int j = i + 1; j < n; ++ j)
        {
           /* for(step = 1; step < n; step <<= 1);

            for(m = j + 1; step; step >>= 1)
                if(m + step <= n && v[m + step] <= v[i] + v[j])
                    m += step;
            if(v[m] > v[i] + v[j]) m --;
            mini = m;

            for(step = 1; step < n; step <<= 1);

            for(m = j + 1; step; step >>= 1)
                if(m + step <= n && v[m + step] < v[j] - v[i])
                    m += step;

            if(v[m] < v[j] - v[i]) m++;
            k += mini - m + 1;
            */st = j + 1;
            dr = n;
            while(st <= dr)
            {
                mij = (st + dr) >> 1;

                if(v[mij] >= v[j] - v[i])
                    dr = mij - 1;
                else
                    st = mij + 1;
            }
            if(v[mij] < v[j]-v[i]) mij ++;

            mini = mij;

            st = j + 1;
            dr = n;
            while(st <= dr)
            {
                mij = (st + dr) >> 1;

                if(v[mij] <= v[i] + v[j])
                    st = mij + 1;
                else
                    dr = mij - 1;
            }
             if(v[j] + v[i] < v[mij]) mij --;

             k+= mij - mini + 1;
        }
    G << k;
    return 0;
}