Cod sursa(job #1383874)

Utilizator bogdanciurezubogdan ciurezu bogdanciurezu Data 10 martie 2015 18:45:03
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <fstream>
#include <algorithm>
#define nmax 900
#define For(i, x, y) for((i) = (x); (i) <= (y); ++(i))

using namespace std;
ifstream f("nrtri.in");
ofstream g("nrtri.out");
int v[nmax], n, nrtr;
int cautbin(int x){
    int st = 1, dr = n, mij, dr1 = n - 1;
    while(st < dr1){
        mij = (st + dr) / 2;
        if(v[mij] == x) return mij;
        else {
            if(v[mij] > x) dr = mij;
            else st = mij + 1;
        }
    }
    return st;
}
int main()
{int i, j, maxim;
    f>>n;
    For(i, 1, n) f>>v[i];
    sort(v + 1, v + n + 1);

    For(i, 1, n){
        For(j, i + 1, n){
            nrtr += j - i - 1;
            maxim = v[i] + v[j];
            nrtr += cautbin(maxim) - j;
        }
    }
    g<<nrtr<<'\n';
    return 0;
}