Cod sursa(job #2296032)

Utilizator cahemanCasian Patrascanu caheman Data 4 decembrie 2018 10:16:58
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.51 kb
#include<cstdio>
#include<algorithm>

using namespace std;

int bete[1000], n;

int cautbindr(int val)
{
    int st, dr, med, last;
    st = 1;
    dr = n;
    while(st <= dr)
    {
        med = (st + dr) >> 1;
        if(bete[med] <= val)
        {
            last = med;
            st = med + 1;
        }
        else
            dr = med - 1;
    }
    return last;
}

int cautbinst(int val)
{
    int st, dr, med, last;
    st = 1;
    dr = n;
    while(st <= dr)
    {
        med = (st + dr) >> 1;
        if(bete[med] >= val)
        {
            last = med;
            dr = med - 1;
        }
        else
            st = med + 1;
    }
    return last;
}

int main()
{
    freopen("nrtri.in", "r", stdin);
    freopen("nrtri.out", "w", stdout);
    int i, j, s = 0, sbete, dbete, st, dr;
    scanf("%d", &n);
    for(i = 1; i <= n; ++ i)
        scanf("%d", &bete[i]);
    sort(bete + 1, bete + n + 1);
    for(i = 1; i <= n; ++ i)
        for(j = 1; j <= n; ++ j)
            if(i != j)
            {
                sbete = bete[i] + bete[j];
                dbete = bete[i] - bete[j];
                if(dbete < 0)
                    dbete = 0 - dbete;
                dr = cautbindr(sbete);
                st = cautbinst(dbete);
                s +=  dr - st + 1;
                if(st <= i && i <= dr)
                    -- s;
                if(st <= j && j <= dr)
                    -- s;
            }
    printf("%d", s / 6);
    return 0;
}