Cod sursa(job #2096559)

Utilizator osiaccrCristian Osiac osiaccr Data 29 decembrie 2017 13:53:52
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <fstream>
#include <algorithm>
#define DEF 810

using namespace std;

ifstream fin ("nrtri.in");
ofstream fout ("nrtri.out");

int n, v[DEF], sol;

int main () {
    fin >> n;
    for (int i = 1; i <= n; ++ i) {
        fin >> v[i];
    }

    sort (v + 1, v + n + 1);

    for (int i = 1; i <= n - 2; ++ i) {
        for (int j = i + 1; j <= n - 1; ++ j) {
            int st = j + 1, dr = n, mid, poz = j;
            while (st <= dr) {
                mid = (st + dr) / 2;
                if (v[mid] <= v[i] + v[j]) {
                    poz = mid;
                    st = mid + 1;
                }
                else {
                    dr = mid - 1;
                }
            }

            sol += poz - j;
        }
    }

    fout << sol;

    return 0;
}