Cod sursa(job #1264980)

Utilizator smaraldaSmaranda Dinu smaralda Data 16 noiembrie 2014 15:47:41
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

#define mid (left + right) / 2
const int NMAX = 803;

int n, len[NMAX];

int bs1 (int left, int val) {
    int last, right;
    
    last = -1;
    right = n;
    while(left <= right) {
        if(len[mid] >= val)
            last = mid,
            right = mid - 1;
        else
            left = mid + 1;
    }

    return last;
}

int bs2 (int left, int val) {
    int last, right;

    last = -1;
    right = n;
    while(left <= right) {
        if(len[mid] <= val)
            last = mid,
            left = mid + 1;
        else
            right = mid - 1;
    }
    return last;
}

int main() {
    freopen("nrtri.in", "r", stdin);
    freopen("nrtri.out", "w", stdout);
    int i, left, right, res, j;

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

    res = 0;
    for(i = 1; i <= n; ++ i)
        for(j = i + 1; j <= n; ++ j) {
            right = bs2(j + 1, len[i] + len[j]);
            left = bs1(j + 1, len[j] - len[i]);

            if(left != -1 && right != -1)
                res += right - left + 1;
        }
    printf("%d\n", res);
    return 0;
}