Cod sursa(job #696085)

Utilizator SchumiDumitru Andrei Georgian Schumi Data 28 februarie 2012 16:42:14
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <cstdio>
#include <algorithm>
using namespace std;

int n, v[1000];
int sol;

int tri(int p, int u, int x, int y)
{
    int mij;
    while(p <= u) {
        mij = (p + u) / 2;
        if((v[x] + v[y] >= v[mij] && v[x] + v[y] < v[mij + 1]) || (v[x] + v[y] >= v[mij] && mij == n))
            return mij;
        else if(v[x] + v[y] >= v[mij] && v[x] + v[y] >= v[mij + 1])
            p = mij + 1;
        else u = mij - 1;
    }
    return 0;
}

int main()
{
    int i, j;
    freopen ("nrtri.in", "r", stdin);
    freopen ("nrtri.out", "w", stdout);
    scanf("%d", &n);
    for(i = 1; i <= n; ++i)
        scanf("%d", &v[i]);
    sort(v + 1, v + n + 1);
    for(i = 1; i < n - 1; ++i)
        for(j = i + 1; j < n; ++j)
            sol += tri(1, n, i, j) - j;
    printf("%d", sol);
    return 0;
}