Cod sursa(job #3371261)

Utilizator MMticaCibu Aida MMtica Data 29 octombrie 2026 15:15:07
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <fstream>
#include <algorithm>
using namespace std;

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

int main() {
    int v[800], n, cnt = 0;
    fin >> n;

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

    for (int i = 0; i < n - 2; i++) {
        for (int j = i + 1; j < n - 1; j++) {
            int start = v[j] - v[i], finish = v[j] + v[i];
            if (start < v[j + 1]) {
                start = v[j + 1];
            }
            if (finish > v[n - 1]) {
                finish = v[n - 1];
            }

            if (start <= v[n - 1] && finish >= v[j + 1]) {
                int st = j + 1, dr = n - 1, pozst = dr, pozdr = st;
                while (st <= dr) {
                    int mij = st + (dr - st) / 2;
                    if (start <= v[mij]) {
                        pozst = mij;
                        dr = mij - 1;
                    }
                    else {
                        st = mij + 1;
                    }
                }
                st = j + 1;
                dr = n - 1;
                while (st <= dr) {
                    int mij = st + (dr - st) / 2;
                    if (finish < v[mij]) {
                        dr = mij - 1;
                    }
                    else {
                        pozdr = mij;
                        st = mij + 1;
                    }
                }
                cnt += pozdr - pozst + 1;
            }
        }
    }

    fout << cnt;

    return 0;
}