Cod sursa(job #1150547)

Utilizator BlackLordFMI Alex Oprea BlackLord Data 23 martie 2014 11:46:45
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <cstdio>
#include <algorithm>
using namespace std;
int n, i, j, v[810], p, u, x, y, nrt;

inline int modul(int x){
    return (x>(-x)?x:(-x));
}

int cb(int x, int t){
    int p=1, u=n, m;
    while(p<=u)
    {
        m=(p+u)/2;
        if(v[m]<=x)
            p=m+1;
        else
            u=m-1;
    }
    if(t==1)
        return u;
    return p;
}

int main(){
    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++)
        {
            x=cb(v[i]+v[j], 1);
            y=cb( modul(v[i]-v[j]), 2);
            nrt+=(x-y+1);
            if(j>=y && j<=x)
                nrt-=(j-y+1);
        }
    printf("%d\n", nrt);
    return 0;
}