Cod sursa(job #1599111)

Utilizator DeehoroEjkoliPop Darian DeehoroEjkoli Data 13 februarie 2016 16:49:42
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <fstream>
#include <algorithm>
#define nmax 805
using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");

int n, v[nmax], numbering;

void read_input() {
    fin >> n;
    for (int i = 1; i <= n; ++i)
        fin >> v[i];
    sort(v + 1, v + n + 1);
}

int bin_search(int lmtL, int j) {
    int one = v[lmtL], two, lmtR = j, three = v[lmtR], pivot, pos = 0;
    while (true) {
        pivot = (lmtL + lmtR) / 2;
        two = v[pivot];
        if (one + two < three) {
            lmtL = pivot;
        }
        if (one + two >= three) {
            lmtR = pivot;
            pos = pivot;
        }
        if (lmtR - 1 == lmtL)
            break;
    }
    if (pos == 0)
        return 0;
    return j - pos;
}

int main()
{
    read_input();
    for (int i = 1; i <= n - 2; ++i)
        for (int j = i + 2; j <= n; ++j)
            numbering += bin_search(i, j);
    fout << numbering;
    return 0;
}