Cod sursa(job #1679604)

Utilizator serban_ioan97Ciofu Serban serban_ioan97 Data 8 aprilie 2016 08:52:10
Problema Numarare triunghiuri Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <cstdio>
#include <algorithm>

using namespace std;

int i, j, n, x, answer;
int length[505];

int b_search(int left, int right, int x)
{
    int best=-1, mid;

    while(left<=right)
    {
        mid=(left+right)>>1;

        if(length[mid]<=x)
        {
            if(mid>best)
            best=mid;
            left=mid+1;
        }

        else right=mid-1;
    }
    return best;
}

int main()
{
    freopen("nrtri.in", "rt", stdin);
    freopen("nrtri.out", "wt", stdout);

    scanf("%d", &n);

    for(i=1; i<=n; ++i)
        scanf("%d", &length[i]);

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

    for(i=1; i<=n; ++i)
    {
        for(j=i+1; j<=n; ++j)
        {
            x=b_search(j+1, n, length[i]+length[j]);
            if(x!=-1) answer+=x-j;
        }
    }

    printf("%d\n", answer);
    return 0;
}