Cod sursa(job #3174527)

Utilizator LuciBBadea Lucian LuciB Data 24 noiembrie 2023 21:04:27
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <bits/stdc++.h>
using namespace std;

FILE *fin, *fout;

const int NMAX = 800;

int v[NMAX];

int main() {


    int n;

    fin = fopen("nrtri.in", "r");
    fscanf(fin, "%d", &n);
    for(int i = 0; i < n; i++) {
        fscanf(fin, "%d", &v[i]);
    }
    fclose(fin);


    /*
     * 3 betisoare formeaza un triunghi <=>
     * a + b >= c, unde a <= b <= c
     * => sortam betisoarele dupa lungime
     * si fixam a si b si cautam binar c-ul maxim
     * pentru care c <= a + b
     * si vom adauga la raspuns numarul de numere
     * dintre b si c, adica pozC - pozB
     */
    sort(v, v + n);
    int ans = 0;
    for(int i = 0; i < n - 2; i++) {
        for(int j = i + 1; j < n - 1; j++) {
            int a = v[i], b = v[j];
            int st = j + 1, dr = n; /// [st, dr)
            while(dr - st > 1) {
                int mij = (st + dr) / 2;
                int c = v[mij];
                if(c > a + b)
                    dr = mij;
                else
                    st = mij;
            }
            if(v[st] <= a + b) {
                ans += st - j;
            }
        }
    }

    fout = fopen("nrtri.out", "w");
    fprintf(fout, "%d", ans);
    fclose(fout);

    return 0;
}